110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

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

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

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

示例 3：

1
2
输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -104 <= Node.val <= 104

题解：

求深度适合用前序遍历，而求高度适合用后序遍历。

此题求高度，使用后序遍历

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
33
public boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}

//-1表示已经不是平衡二叉树了，否则返回值是以该节点为根节点的树的高度
private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    //左
    int leftHeight = getHeight(root.left);
    if (leftHeight == -1) {
        return -1;
    }

    //右
    int rightHeight = getHeight(root.right);
    if (rightHeight == -1) {
        return -1;
    }

    //中
    int result;
    //左右子树高度差大于1，则不是平衡二叉树
    if (Math.abs(leftHeight - rightHeight) > 1) {
        result = -1;
    } else {
        result = Math.max(leftHeight, rightHeight) + 1;
    }

    return result;

}
  • 时间复杂度：O(N)。N为二叉树的节点个数。自底向上递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点。
  • 空间复杂度：O(N)。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n。