110. 平衡二叉树

原题链接：110. 平衡二叉树

为什么求深度是前序遍历？
前序是中左右，他不是向上返回结果，而是一层一层往下走，符合从顶部到底部的统计 所以求深度适合前序遍历

为什么求高度是后序遍历？
后续是左右中,是从底部一层一层往上返回结果，就很适合统计某个叶子结点的高度
因为高度层层向上返回，每个父节点加上自己的高度(+1) 才统计得到了根节点高度

平衡二叉树：
左子树和右子树的高度差小于等于1，求高度的话 需要使用后续遍历。
一起判断左右子树的高度，然后在遍历到中时，进行左右子树高度判断，如果大于1则不是高度的平衡二叉树 返回-1
如果不大于1 则代表是高度平衡的二叉树，且返回该层+最大的子树高度

全代码：

class Solution {
public:
    int gethight(TreeNode* Node)
    {//左右中
        //左
        //先判断是否是空树，是的话返回0
        if(Node == NULL) return 0;
        //传入左子树，判断高度是否为-1
        int left_hight = gethight(Node -> left);
        if(left_hight ==  -1) return -1;
        //传入右子树，判断高度是否为-1
        int right_hight = gethight(Node ->right);
        if(right_hight == -1) return -1;
        //中
        int result;
        //如果左子树-右子树的高度的绝对值大于一 则代表不符合条件 返回-1
        if(abs(left_hight - right_hight) > 1)  return -1;
        else
        {//如果符合条件，返回该层高度+最大的子树高度
            result = 1 + max(left_hight,right_hight);
        }
        return result;
    }

    bool isBalanced(TreeNode* root) {
        int result = gethight(root);
        if(result == -1) return false;
        else return true;


    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32