通过深度判断二叉树是否平衡

题目链接-来源：力扣（LeetCode）

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3

/
9 20
/
15 7
返回 true 。

思路：

借鉴上一题的方法，我们利用 DFS 就能递归地获取到二叉树的每个子树深度。但是对于某个节点来说，除了子树深度的信息，我们还需要知道子树中是否已经发生了「不平衡」。
这里我们可以巧妙地在返回值中增加这个信息，若没有不平衡，正常返回子树最大深度 + 1；否则，返回一个负值告诉上层节点已经出现了不平衡。
这样我们就用一个变量同时传递了子树深度和是否存在不平衡的两条信息。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isBalanced(TreeNode root) {
        return (depthHelper(root) != -1);
    }
    private boolean isBalanced = true;
    private int depthHelper(TreeNode root) {
        if (isBalanced) {
            if (root == null) {
                return 0;
            }
            int left = depthHelper(root.left), right = depthHelper(root.right);
            if (left == -1 || right == -1 || left - right > 1 || right - left > 1) {
                return -1;
            }
            return Integer.max(left, right) + 1;
        }
        return -1;
    }
}