平衡二叉树

约 1652 字大约 6 分钟

2025-03-01

110. 平衡二叉树

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：true

提示：

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

有返回值无信息参数的DFS，嵌套DFS

自顶向下递归，递归地计算左右子树的深度，如果左右子树的深度差超过1，返回false。否则递归地检查左右子树是否也是平衡的。

class Solution {
    // 以root为根节点的左右子树的高度差的绝对值小于等于1，这不能确保该树是平衡二叉树，因为我们要确保每个子节点的左右子树的高度差都不大于1
    public boolean isBalanced(TreeNode root) {
        // 特殊条件：如果根节点是空，那么它自然是平衡的
        if (root == null) {
            return true;
        }
        
        // 递归地计算左子树的深度
        int leftDepth = getTreeDepth(root.left);
        // 递归地计算右子树的深度
        int rightDepth = getTreeDepth(root.right);
        // 如果左右子树的深度差超过1，那么按照定义，这不是一个平衡的二叉树
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        // 注意这里不能直接返回true，还要递归地检查左右子节点的左右子树的高度差的绝对值是否小于等于1
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int getTreeDepth(TreeNode root) {
        // 如果节点为空，返回深度0
        if (root == null) {
            return 0;
        }
        
        // 递归获取左子树的深度
        int leftDepth = getTreeDepth(root.left);
        // 递归获取右子树的深度
        int rightDepth = getTreeDepth(root.right);
        // 当前节点的深度为左右子树深度的最大值加1（加的1代表当前节点本身的高度贡献）
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

对每个节点都计算一次深度，因此时间复杂度是 $O(n^2)$

时间复杂度: $O\left(n^2\right)$ ，其中 $n$ 是二叉树中的节点个数。最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 $O(n)$ 。对于节点 $p$ ，如果它的高度是 $d$ ，则 $\operatorname{height}(p)$ 最多会被调用 $d$ 次 (即遍历到它的每一个祖先节点时)。对于平均的情况，一棵树的高度 $h$ 满足 $O(h)=O(\log n)$ ，因为 $d \leq h$ ，所以总时间复杂度为 $O(n \log n)$ 。对于最坏的情况，二叉树形成链式结构，高度为 $O(n)$ ，此时总时间复杂度为 $O\left(n^2\right)$ 。
空间复杂度: $O(h)$ ，其中 $h$ 是二叉树的高度。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$ 。

后序，返回值双重意义。

大于零时表示深度，小于零时表示不平衡。平衡时返回深度，不平衡时返回-1.

自底向上，递归方法重复计算了子树的高度。事实上，计算完左右子树的高度就可以判断该树是否是平衡的了。

方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数)，否则返回 -1 。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

即当我们求左子树的高度时，同样是利用了递归去求它的左子树的高度和右子树的高度。

当代码执行到

isBalanced(root.left) && isBalanced(root.right)

递归的判断左子树和右子树是否是平衡二叉树的时候，我们又会继续求高度，求高度再次进入 getTreeDepth 函数的时候，我们会发现，其实在上一次这些高度都已经求过了。

第二个不好的地方在于， getTreeDepth 递归的求高度的时候，也是求了左子树的高度，右子树的高度，此时完全可以判断当前树是否是平衡二叉树了，而不是再继续求高度。

综上，我们其实只需要求一次高度，并且在求左子树和右子树的高度的同时，判断一下当前是否是平衡二叉树。

考虑到 getTreeDepth 函数返回的是int值，同时高度不可能为负数，那么如果求高度过程中我们发现了当前不是平衡二叉树，就返回-1。

private int getTreeDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = getTreeDepth(root.left); 
    int rightDepth = getTreeDepth(root.right); 
    if (Math.abs(leftDepth - rightDepth) > 1) {
        return -1;
    }
    return Math.max(leftDepth, rightDepth) + 1;
}

上边的代码还是有问题的，

int leftDepth = getTreeDepth(root.left); 
int rightDepth = getTreeDepth(root.right);

如果左右子树都不是平衡二叉树，此时都返回了-1，那么再执行下边的代码。

if (Math.abs(leftDepth - rightDepth) > 1) {
    return -1;
}

它们的差会是 0，不会进入if中，但是本来应该进入 if 返回 -1 的。

所以当发现 leftDepth返回 -1 的时候，我们需要提前返回 -1。rightDepth也会有同样的问题，所以也需要提前返回 -1。

正确的解法如下：

public boolean isBalanced(TreeNode root) {
    return getTreeDepth(root) != -1;
}

private int getTreeDepth(TreeNode root) {
    if (root == null) {
        return 0; // 注意null也是平衡二叉树
    }
    
    int leftDepth = getTreeDepth(root.left);
    if (leftDepth == -1) {
        return -1;
    }
    int rightDepth = getTreeDepth(root.right);
    if (rightDepth == -1) {
        return -1;
    }
    
    if (Math.abs(leftDepth - rightDepth) > 1) {
        return -1;
    }
    return Math.max(leftDepth, rightDepth) + 1;
}

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