题目链接：Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

这道题的要求是判断一个二叉树是否高度平衡。所谓高度平衡，就是指二叉树中每个节点的左右子树的最大深度相差不超过1。

考虑递归思路，处理当前节点是，通过Maximum Depth of Binary Tree计算出左右子树的深度，然后判断是否相差小于1。同时还需要递归判断左右子树是否也是高度平衡的二叉树。

可以注意到，在处理某节点的时候，需要遍历2次其子树（求深度和判断是否高度平衡），时间复杂度较高。接下来可以采用一个技巧，就是在求深度的时候同时判断是否平衡，然后对于不平衡的直接返回-1作为标记，这样降低了时间复杂度。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    bool isBalanced(TreeNode *root)
    {
        return maxDepth(root) != -1;
    }
private:
    int maxDepth(TreeNode *p)
    {
        if(p == NULL)
            return 0;
        
        int lh = maxDepth(p -> left);
        int lr = maxDepth(p -> right);
        
        if(lh == -1 || lr == -1 || abs(lh - lr) > 1)
            return -1;
        
        return max(lh, lr) + 1;
    }
};