代码随想录训练营-15day：二叉树4

一、平衡二叉树

平衡二叉树的定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

使用递归方式：首先需要知道高度是什么意思，怎么获取高度。如果高度差大于1了，那么回复高度就没有意义了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int getHight(struct TreeNode* root)//得到左右子树的高度差
{
    if(root == NULL)
    {
       return 0;
    }
    int left_len = getHight(root->left);
    if(left_len == -1) return -1;
    int right_len = getHight(root->right);
    if(right_len == -1) return -1;
    return  abs(right_len - left_len) > 1? -1 : 1 + (right_len > left_len? right_len : left_len);
}

bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    int len = getHight(root);
    return len == -1? false : true;
}

二、二叉树所有路径

主要是理解递归+回溯的思路，每一次递归之后，需要回退，把路径搜索完成，遍历一个完整的路径。解答过程遇到两个方面的问题：

1 就是打印函数，sprintf使用不当，导致保存出错；之前使用的数字转字符函数和strcat，没使用成功；

2 就是c语言写法，需要传入top在里面，因此按照代码随想录的思路，先把value入栈，top在递归过程，会变化，导致元素缺失，因此需要把入栈操作放到判断左右子树的条件里面。

#define ARRNUM 101
void trans(struct TreeNode* curNode, char** result, int* stk, int* returnSize, int top)
{ 
    //stk[top++] = curNode->val;//stack push
    //printf(" %d -> %d\n", top, stk[top]);
    // if(curNode == NULL)
    //   return;
    if(curNode->left == NULL && curNode->right == NULL)
    {
        int len = 0;
        for(int i = 0; i < top; i++)//top is "0" index start
        {
            len += sprintf(result[(*returnSize)] + len, "%d->", stk[i]);
            //printf("val = %d\n",stk[i]);
        }
        //printf("top = %d\n", top);
        sprintf(result[(*returnSize)] + len, "%d", curNode->val);
        (*returnSize)++;//push到result
        return;
    }
    if(curNode->left)
    {
       stk[top++] = curNode->val;
       trans(curNode->left, result, stk, returnSize, top);
       --top;//value stack pop
       //printf("/top = %d\n", top);
    }
    
    if(curNode->right)
    {
       stk[top++] = curNode->val;
       trans(curNode->right, result, stk, returnSize, top);
       --top;//value stack pop
       //printf("//top = %d\n", top);
    }
    
}
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    /**定义字符数组**/
    char** result = (char**)malloc(sizeof(char*) * ARRNUM);//定义100个字符串
    for(int i = 0; i < ARRNUM; i++)
    {
        result[i] = (char*)malloc(ARRNUM);//每个字符串定义100长度
    }
    *returnSize = 0;
    if(root == NULL)
      return result;
    /**定义保存节点值的数组模拟栈**/
    int* stack = (int*)malloc(sizeof(int) * 1024);
    int top = 0;//栈的位置
    trans(root, result, stack, returnSize, top);
    return  result;
}

三、左叶子之和

重点是理解左叶子节点的含义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点（代码随想录的解释）

int sumOfLeftLeaves(struct TreeNode* root){
    //递归出口
    if(root == NULL)
       return 0;
    if(root->left == NULL && root->right == NULL)//没有左y右子树， 不存在左叶子节点
      return 0;
    int leftvalue = sumOfLeftLeaves(root->left);
    if(root->left && root->left->left == NULL && root->left->right ==NULL)
    {
        leftvalue = root->left->val;//保存当前叶子节点的值
    }
    //右子树的左叶子节点
    int rightvalue = sumOfLeftLeaves(root->right);

    return leftvalue + rightvalue;
}