LeetCode 面试题 04.04. 检查平衡性
目录
题目描述
题意分析
判断一棵二叉树是否平衡。这里的平衡定义是：树中每一个节点的左右子树高度差都不超过 1，只要有一个节点违反就返回假。
定义里的「每一个节点」是最容易被读漏的关键词。它意味着这不是对根做一次判断，而是对全部
n个节点做同一个判断；只检查根的左右子树高度差，会漏掉深处那些局部失衡的结构。判定所需的原料是「子树高度」，而高度这个量天然自底向上产生——一个节点的高度由孩子的高度决定。这就给出了处理顺序的信号：必须先拿到孩子的结果，才能算当前节点的结果，也才能顺带做当前节点的判定。
边界：空树是平衡的，高度记为 0；单节点树平衡，高度为 1；只有一个孩子的节点，另一侧按空子树的高度 0 参与计算，此时高度差恰好是 1，仍然合法。
解法：深度优先搜索
核心思路
最直接的写法是「对每个节点求一次左右子树高度并比较」：外层递归遍历所有节点，内层再递归求高度。它是对的，但同一棵子树的高度被反复计算——外层走到深度
d的节点时，它下面的子树已经在祖先的判定中被完整量过一遍了。最坏情况（链状树）下退化成平方级。瓶颈在于「求高度」和「判平衡」被拆成了两趟独立的递归，前者的结果没有被后者复用。观察一下这两件事的依赖关系：求某节点的高度必须先求出两个孩子的高度，而判某节点是否平衡需要的恰好也是这两个高度。它们的原料完全相同，完全可以在同一次后序遍历里一次算完。
于是把返回值的语义合并成一个整数，这是本题的核心设计：
dfs(root)返回以root为根的子树高度，但如果这棵子树内部存在失衡节点，就返回 -1 作为哨兵。高度恒为非负，所以 -1 不会与任何合法高度混淆，一个int就同时承载了「多高」和「是否合法」两份信息。递归的不变量随之确定：任意一次
dfs(x)返回后，要么返回值等于x子树的真实高度且该子树内所有节点都平衡，要么返回 -1 且该子树内至少有一个节点失衡。基于这条不变量，dfs(root) >= 0就是最终答案。
解题步骤
- 递归基：
root == null返回 0。空子树高度为 0，且天然平衡，直接落入合法分支，不需要单独的空树特判。- 先取两个孩子的结果：
l = dfs(root.left)、r = dfs(root.right)。两次递归必须都执行完再做判断，这也是后序遍历的含义——当前节点的处理排在两棵子树之后。- 三合一的失败判定：
l < 0 || r < 0 || Math.abs(l - r) > 1时返回 -1。前两项是「孩子那边已经发现失衡」的传播，第三项是「当前节点自己失衡」的发现；三者任一成立，整棵子树就被打上失败标记，且这个标记会沿着第一项、第二项一路冒到根。- 正常返回高度：
Math.max(l, r) + 1。走到这一步说明两个孩子都合法且当前节点也合法，此时返回的才是真实高度。加一代表当前节点自身这一层。- 入口转布尔：
return dfs(root) >= 0。哨兵值的解码只在入口做一次，递归内部一律用整数流转。以失衡用例
[1, 2, 2, 3, 3, null, null, 4, 4]走一遍：根为 1，左孩子 2 有两个孩子 3、3，其中左边那个 3 又有两个孩子 4、4；根的右孩子 2 是叶子。后序推进：四个 4 都是叶子，各返回 1；它们的父节点 3 得
l = r = 1，差为 0，返回 2；另一个 3 是叶子返回 1；左边的 2 拿到l = 2、r = 1，差为 1 合法，返回 3；右边的 2 是叶子返回 1；轮到根 1，l = 3、r = 1，差为 2 大于 1，返回 -1。入口判断-1 >= 0不成立，答案为假。再看平衡用例
[3, 9, 20, null, null, 15, 7]：叶子 9、15、7 各返回 1；节点 20 的两个孩子都返回 1，差为 0，返回 2；根 3 拿到l = 1、r = 2，差为 1 合法，返回 3。入口判断3 >= 0成立，答案为真。注意这一趟里每棵子树的高度只被算了一次，没有任何重复求高度的调用。
代码实现
class Solution {
public boolean isBalanced(TreeNode root) {
return dfs(root) >= 0;
}
// 返回子树高度；子树内存在失衡节点时返回 -1。
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
if (l < 0 || r < 0 || Math.abs(l - r) > 1) {
return -1;
}
return Math.max(l, r) + 1;
}
}
func isBalanced(root *TreeNode) bool {
// 返回子树高度；子树内存在失衡节点时返回 -1。
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := dfs(root.Left), dfs(root.Right)
if l == -1 || r == -1 || abs(l-r) > 1 {
return -1
}
return max(l, r) + 1
}
return dfs(root) >= 0
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$O(n)$，
n为节点数。每个节点只被访问一次，节点内部只做常数次比较与取最大值；把判平衡与求高度合并到同一趟后序遍历，正是它优于「逐点求高度」的 $O(n^2)$ 写法的原因。- 空间复杂度：$O(h)$，
h为树高，来自递归调用栈。树退化成链时为 $O(n)$，平衡时为 $O(\log n)$；除栈之外没有任何额外结构。
关键点总结
- 当「判定」和「计算」需要的原料相同时，就把它们合并进同一次遍历，用一个返回值同时携带两份信息——这是树形递归里最常用的降复杂度手段。
- 哨兵值的前提是它落在合法值域之外：高度恒为非负，所以 -1 可以安全地表示失败；如果被检查的量本身可能为负，就必须换成额外的布尔字段或包装类型。
- 后序遍历的本质是「当前节点的结果依赖孩子的结果」，看到这种依赖方向就应该条件反射地写成先递归后处理。
- 失败标记要能沿着递归链一路冒到根，所以判定条件里必须先检查两个孩子是否已经返回 -1，漏掉这一步会让深处的失衡被上层用错误的高度覆盖掉。
- 面试时要能主动说清「平衡的定义是对每个节点成立，不是只对根成立」，并给出 $O(n^2)$ 朴素解与 $O(n)$ 合并解的对比；这两点是这道题真正的考查目标。
易错点总结
- 只判断根的左右子树高度差：
[1, 2, 2, 3, null, null, 3, 4, null, null, 4]这类两侧总高度相同但内部失衡的树 → 根的差为 0 被判为真，实际深处存在差为 2 的节点。- 忘了传播孩子的 -1：把条件写成只判
Math.abs(l - r) > 1→[1, 2, 2, 3, 3, null, null, 4, 4]中左子树已返回 -1，abs(-1 - 1) = 2这次碰巧仍然拦下，但换成右子树也返回 -1 的用例时abs(-1 - (-1)) = 0直接放行，失衡被吞掉。- 递归基返回 -1 或 1：空树返回 -1 会让每个叶子的父节点误判为失衡；返回 1 则整棵树的高度全部偏大 1，虽然差值不变但与「空树高度为 0」的约定冲突，混用两种约定时必然出错。
- 判定阈值写成
>= 1：[1, 2, null]→ 根的左右高度为 1 和 0，差恰为 1 属于合法，被误判为假。- 求高度时写成
l + r + 1：[1, 2, 3]→ 根返回 3 而不是 2，越往上偏差越大，很快触发虚假的失衡。- 先做判定再递归：在取得
l、r之前就比较，两者尚未赋值或仍是初值，判定结果与树结构无关。- 短路求值导致漏遍历：把两次递归写进同一个
||表达式（如if (dfs(root.left) < 0 || dfs(root.right) < 0)）→ 左子树返回 -1 时右子树整棵不再被访问，虽然本题只要布尔答案还能过，但一旦题目改成同时统计节点数就会少算。- 用
Math.abs却让参数溢出：把高度换成用Integer.MIN_VALUE当哨兵 →Math.abs(Integer.MIN_VALUE)仍是负数，判定失效。- 外层再包一层遍历重复求高度：链状树
[1, null, 2, null, 3, ...]共 5000 个节点 → 每个节点都重新量一遍子树高度，调用次数达到平方级，直接超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 110. 平衡二叉树 | 简单 | 与本题同题，进阶要求正是把 $O(n^2)$ 的逐点求高优化成一趟后序 |
| 104. 二叉树的最大深度 | 简单 | 只求高度不做判定，是本题递归返回值去掉哨兵后的裸骨架 |
| 111. 二叉树的最小深度 | 简单 | 取最小值时必须排除空孩子那一侧，否则单边节点会把深度算成 1 |
| 543. 二叉树的直径 | 简单 | 同样在后序里顺带更新全局答案，但答案是左右高度之和而非差 |
| 124. 二叉树中的最大路径和 | 困难 | 返回值只能带单侧链，全局答案另存，是「返回值与答案分离」的进阶 |
| 559. N 叉树的最大深度 | 简单 | 孩子数不定，需在孩子列表上取最大值再加一 |
| 剑指 Offer 55 - II. 平衡二叉树 | 简单 | 与本题同题，可直接套用哨兵返回值的写法 |