平衡二叉树 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

平衡二叉树是指：二叉树的每个节点的左右两个子树的高度差的绝对值不超过 1。

树中节点数在 [0, 5000] 内，节点值在 [-10⁴, 10⁴] 范围内。

示例 1

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

输出：true

根左右子树高度分别为 1 与 2，差为 1；子树自身也平衡。

示例 2

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

输出：false

节点 3 的左子树高度 2、右子树高度 0，差为 2，整棵树不平衡。

示例 3

输入：root = []

输出：true

空树视为平衡。

💭 模拟答题者思考

1. 暴力直觉：对每个节点分别算左右子树高度（两次 #104），比较差值是否 ≤ 1，再递归左右孩子是否平衡——正确，但共享子树会被重复算高度，最坏 O(n²)。

2. 重复在哪里？「子树是否平衡」与「子树高度」在同一次后序遍历里就能一并得出，不必为每个节点单独再起一套高度 DFS。

3. 自底向上：后序先拿左右高度；若某侧已是 -1（子树已不平衡）直接向上传 -1；若 |left-right| > 1 当前子树也不平衡，返回 -1；否则返回 1 + max(left, right) 供父节点使用。

4. 示例 2：最深不平衡出现在节点 3，左高 2、右高 0，该层 dfs 返回 -1，一路传到根，isBalanced 为 false。

5. 每个节点访问常数次，时间 O(n)；递归栈 O(h)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`dfs(node)`	int	定义：以 `node` 为根的子树若平衡则返回其高度（空树 0）；若已发现不平衡则返回 `-1` 作哨兵维护：后序汇总左右子树高度后，在当前节点处校验 `\|left - right\| ≤ 1` 更新：左右任一返回 `-1` 则向上传播 `-1`；否则 `return 1 + max(left, right)`
`left, right`	int	定义：当前节点左、右子树的高度（由子递归 `dfs` 给出）维护：子树必须已平衡，否则值为 `-1`，父层不再计算差值更新：`left = dfs(node.left)`，`right = dfs(node.right)`
`isBalanced(root)`	bool	定义：整棵树是否平衡维护：等价于「自顶向下一次 DFS 能否走完且从未触发哨兵」更新：`return dfs(root) != -1`

⌨️ 落码步骤

1. 定义 dfs(node)：若 node 为空返回 0

2. left = dfs(node.left)，若 left == -1 返回 -1

3. right = dfs(node.right)，若 right == -1 返回 -1

4. 若 abs(left - right) > 1 返回 -1，否则 return 1 + max(left, right)

5. isBalanced 返回 dfs(root) != -1

💻 代码实现

class Solution:
    def isBalanced(self, root: TreeNode | None) -> bool:
        def dfs(node: TreeNode | None) -> int:
            if not node:
                return 0
            left = dfs(node.left)
            if left == -1:
                return -1
            right = dfs(node.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return dfs(root) != -1

class Solution {
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        if (left == -1) return -1;
        int right = dfs(node->right);
        if (right == -1) return -1;
        if (std::abs(left - right) > 1) return -1;
        return 1 + std::max(left, right);
    }

public:
    bool isBalanced(TreeNode* root) {
        return dfs(root) != -1;
    }
};
// 时间 O(n)，空间 O(h)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(h)（递归栈，h 为树高；链状树最坏 O(n)）

⚠️ 常见坑

❗ 只检查根节点左右高度差：子树内部不平衡也会被判为 false，必须递归或在一次 DFS 里让子树结果参与判断。

❗ 高度定义与 #104 不一致：本题高度是节点层数（空 0、单节点 1），差值比较要用同一套定义。

❗ 发现不平衡仍继续算高度：应尽早返回哨兵 -1，避免无意义遍历（朴素双 DFS 虽能过中小数据，但面试应写 O(n) 版）。

🔍 必测边界 Case

Case 1：空树

root = [] → true

Case 2：单节点

root = [1] → true

Case 3：官方示例 1（平衡）

root = [3,9,20,null,null,15,7] → true

Case 4：官方示例 2（不平衡）

root = [1,2,2,3,3,null,null,4,4] → false

Case 5：仅根不平衡、一侧为空

root = [1,2,null,3,null,4] → false（左链深度 > 1）