输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1：

**输入：**root = [3,9,20,null,null,15,7]
**输出：**true
**解释：**如下图

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]

输出：false

解释：如下图

提示：

0 <= 树的结点个数 <= 10000

首先想到分别计算左右子树深度，再比较，之后再分别判断左右子树

在计算树深度的过程中，我们其实已经计算过所有左右子树深度了（max(left,right)）

所以在取max前我们可以直接判断相差是否大于一，如果大于一则可以直接一路返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isBalanced(TreeNode *root) { return depth(root) != -1; }
    int depth(TreeNode *root) {
        if (root == nullptr)
            return 0;

        int left = depth(root->left);
        if (left == -1)
            return -1;

        int right = depth(root->right);
        if (right == -1)
            return -1;

        if (abs(left - right) > 1)
            return -1;
        return max(left, right) + 1;
    }
};