LeetCode 面试题 04.04. 检查平衡性
题目描述
题意分析
判断二叉树的每个节点是否都满足左右子树高度差不超过 1。根节点看起来平衡并不能说明整棵树平衡，任意后代失衡都要返回失败。
解法：后序同时返回高度与失衡标记
核心思路
[!blue]
判断一个节点是否平衡需要先知道左右子树高度，所以从叶子向上做后序遍历。若在每个节点重新计算两侧高度，会反复访问同一批后代；让递归顺便返回高度，就能把所有判断合并到一次遍历中。
约定
dfs(node)的返回值有两种含义：非负数表示这棵子树已经确认平衡，同时给出它的高度；-1表示子树中至少有一个失衡节点。空树高度为 0，非空树高度至少为 1，因此-1不会与合法高度混淆。取得左右结果
l、r后，若任一结果为-1，当前子树也不可能平衡，继续上传失败标记。否则两侧内部都已平衡，只需检查当前节点的高度差：超过 1 就返回-1，不超过 1 才返回max(l, r) + 1。这样每层都同时验证了子树内部和当前根的条件，最终根返回非负值才说明所有节点都平衡。空树返回高度 0，因此也自然判为平衡。
解题步骤
- 空节点返回高度 0。
- 后序取得左右结果。
- 任一为 -1 或高度差超过 1，就返回 -1。
- 否则返回 max(left,right)+1；根结果非负表示平衡。
代码实现
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)$，每个节点只计算一次高度和失衡状态。
- 空间复杂度：$O(h)$，用于递归栈；树退化为链时为 $O(n)$。
关键点总结
[!green]
非负高度意味着整棵子树已验证通过，
-1使任意深处的失衡都能一路传到根；父节点无需重新遍历已经处理的后代。
易错点总结
[!yellow]
- 不能只检查根的左右高度差。
- 发现子树失衡后不能把 -1 当正常高度参与最终高度计算。
- 平衡限制是高度差，不是左右节点数之差。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 复用后序求高度，再增加失衡标记的传播。 |
| 543. 二叉树的直径 | 简单 | 同样把子树高度作为返回值，并在父节点结合左右信息计算另一种树性质。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！