LeetCode 剑指 Offer 55 - II. 平衡二叉树
题目描述
题意分析
判断二叉树是否高度平衡：每一个节点的左右子树高度差都不超过 1。条件要对整棵树的所有节点成立，因此只比较根的左右高度不够；空树也属于平衡树。
解法：后序剪枝
核心思路
[!blue]
判断当前子树，需要先知道左右子树是否平衡以及各自的高度，适合用后序遍历自底向上汇总。让
height(node)同时传递这两种信息：子树平衡时返回真实高度，不平衡时返回 -1。合法高度从 0 开始，不会与失败标记混淆。空节点返回 0。先递归求左子树，得到 -1 就直接返回，不必继续检查右边；右子树失败时也一样。两边都平衡后，若高度差超过 1，当前子树仍然不平衡；否则返回
max(left, right) + 1。一处失衡就足以使整棵树不平衡，-1 会沿父节点一直传回根。每个被访问的节点只计算一次高度，避免在每个节点重新遍历左右子树。
解题步骤
- 当前节点为空，返回高度 0。
- 递归取得左子树高度
left，若为 -1，立即返回 -1。- 递归取得右子树高度
right，若为 -1，立即返回 -1。- 两个高度相差超过 1 时返回 -1，否则返回较大高度加 1。
- 根节点的返回值不是 -1，就说明整棵树平衡。
代码实现
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
// 平衡子树返回非负高度，任一失衡则返回负一。
private int height(TreeNode node) {
if (node == null) {
return 0;
}
int left = height(node.left);
// 负一表示子树已失衡，直接上传，不再把它当高度。
if (left == -1) {
return -1;
}
int right = height(node.right);
if (right == -1) {
return -1;
}
// 两侧各自平衡后，还需检查当前节点的高度差。
if (Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
}
func isBalanced(root *TreeNode) bool {
return height(root) != -1
}
// 平衡子树返回非负高度，任一失衡则返回负一。
func height(node *TreeNode) int {
if node == nil {
return 0
}
left := height(node.Left)
// 负一表示子树已失衡，直接上传，不再把它当高度。
if left == -1 {
return -1
}
right := height(node.Right)
if right == -1 {
return -1
}
// 两侧各自平衡后，还需检查当前节点的高度差。
if left-right > 1 || right-left > 1 {
return -1
}
if left > right {
return left + 1
}
return right + 1
}
复杂度分析
- 时间复杂度：$O(n)$，其中
n为节点数；每个节点至多访问一次，提前发现失衡时可能更早结束。- 空间复杂度：$O(h)$，递归栈深度等于树高
h；最坏链状树为 $O(n)$。
关键点总结
[!green]
- 负一与所有合法高度区分开，必须在求最大值之前检查。
- 空树返回零，因此属于平衡树。
- 左右子树各自平衡、当前节点高度差合格，三个条件缺一不可。
易错点总结
[!yellow]
- 只判断根节点会遗漏内部失衡。
- 把失败记为零，会与空子树高度混淆。
- 只比较
left - right > 1会漏掉右边更高的情况，必须检查高度差的绝对值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 后序求高度是基础，本题同时把子树是否失衡的信息向上传递。 |
| 543. 二叉树的直径 | 简单 | 同样用左右子树高度在当前节点计算附加结果，原题求最长路径长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！