LC110 平衡二叉树：不是看根，是每个节点都要过安检 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC110

题型地图 56天全屏 141题

当前：LC110 · 平衡二叉树：不是看根，是每个节点都要过安检 · 首次出现于 Day 20 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC109 LC112 →

48 / 141回到 Day 20 卡片 141 题索引

LC110 · 平衡二叉树 · 工程执行实验室

不是看根，是每个节点都要过安检

后序 DFS，从叶子往上返回高度；一旦发现不平衡，用 -1 向上传警报。在求高度的过程中顺手检查平衡。

复杂度

时间 O(n)

空间 O(h)，最坏 O(n)，平衡树 O(log n)

核心 · 后序高度 + -1 哨兵

check(node) 返回子树高度；若子树不平衡则返回 -1 向上传播。

· 这题不是单纯求高度，而是在求高度的过程中顺手检查平衡。
· 后序遍历的原因是：你必须先知道左右子树的结果，才能判断当前节点。
· -1 是一个哨兵值，表示这棵子树已经不平衡。
· 只检查根节点是错的，因为平衡二叉树要求每一个节点都平衡。

check(node) 五步骤

node == nil → 0
left == -1 → -1
right == -1 → -1
|left − right| > 1 → -1
return max(left, right) + 1

后序 DFS：left → right → root

1.left = check(node.Left) — 左子树先递归，收到高度或 -1。
2.若 left == -1，直接 return -1，不再看右子树。
3.right = check(node.Right)；同样处理 -1 传播与 diff 检查。
4.diff ≤ 1 则 return max(left, right)+1；否则 return -1。

1/8 · 题目目标

8 步分镜：

Step 1题目目标

题目目标：每个节点都要过安检

判断一棵二叉树是否平衡：任意节点的左右子树高度差不能超过 1，且左右子树本身也必须平衡。这不是只看根——整棵树的每一个节点都要满足 abs(leftHeight − rightHeight) ≤ 1。

平衡条件：每个节点都满足 |leftHeight − rightHeight| ≤ 1，且左右子树本身也要平衡。
这题不是单纯求高度，而是在求高度的过程中顺手检查平衡。
后序遍历的原因是：你必须先知道左右子树的结果，才能判断当前节点。
-1 是一个哨兵值，表示这棵子树已经不平衡。
只检查根节点是错的，因为平衡二叉树要求每一个节点都平衡。

为什么正确

平衡条件：每个节点都满足 |leftHeight − rightHeight| ≤ 1，且左右子树本身也要平衡。

状态表 · 树节点 + 递归栈 + 返回值同步

当前节点	调用栈	本层返回	机器状态
3（root）	[]	—	读题平衡定义 · 全树约束

返回值表 · height 或 -1

节点	路径	check 返回
3	root	—
9	left	—
20	right	—
15	right.left	—
7	right.right	—

当前计算

∀ node: |height(left) − height(right)| ≤ 1

且 left、right 子树本身也要平衡

树结构·高亮 = 当前访问·绿 = 高度·红 = -1 警报

递归栈 · dfs(node) 入栈 / 出栈

（空栈 · 递归完成）

Go · check / isBalanced

1func check(node *TreeNode) int {
2    if node == nil {
3        return 0
4    }
5    left := check(node.Left)
6    if left == -1 {
7        return -1
8    }
9    right := check(node.Right)
10    if right == -1 {
11        return -1
12    }
13    if abs(left-right) > 1 {
14        return -1
15    }
16    if left > right {
17        return left + 1
18    }
19    return right + 1
20}
22func isBalanced(root *TreeNode) bool {
23    return check(root) != -1
24}

复杂度

时间: O(n)
空间: O(h)，最坏 O(n)，平衡树 O(log n)

每个节点只访问一次，n 为节点总数。

递归调用栈深度等于树高 h。平衡树约 O(log n)，单链退化最坏 O(n)。不是 O(1)。

面试回答

我会用后序 DFS。递归函数返回当前子树高度，如果发现某个子树不平衡，就返回 -1 作为哨兵值。当前节点先递归计算左右子树高度，如果任意一边返回 -1，说明子树已经不平衡，继续向上传 -1；否则判断左右高度差是否超过 1，超过就返回 -1，不超过就返回 max(left, right)+1。最后判断根节点返回值是否为 -1。每个节点只访问一次，所以时间 O(n)，递归栈空间 O(h)。

常见误区

误区 1：只检查根节点左右高度差

根节点 diff ≤ 1 不代表整棵树平衡。子树内部可能早已不平衡，必须每个节点都过检。

误区 2：空间复杂度写成 O(1)

递归 DFS 需要系统调用栈保存暂停状态，空间是 O(h)，最坏单链 O(n)，不是 O(1)。

误区 3：把 -1 当成高度参与 max

-1 是哨兵警报，不是高度。收到 -1 应立刻向上传播，不再计算 diff 或 max。

误区 4：用前序或中序无法一次 DFS 搞定

判断当前节点是否平衡，必须先知道左右子树的返回结果，所以顺序必须是 left → right → root。

迁移练习

LC104 · 最大深度

同样后序返回高度，但 LC110 在合并前多一步平衡检查，失败则返回 -1。

LC543 · 二叉树直径

也依赖左右子树高度，但答案是 left + right（经过该节点的最长路径）。

LC98 · 验证 BST

同样是整棵树每个节点都要满足约束，不能只看根。