#110
简单
低频
自底向上+递归法平衡二叉树
这是一道围绕树、二叉树展开的高频练习。建议先掌握「自底向上+递归法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
题目分析
这道题表面上是在处理「平衡二叉树」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 树、二叉树 这些能力。这类题更像在一棵决策树里向下展开，关键是递归时带什么状态、什么时候回退。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：递归返回子树高度；一旦发现某个节点左右高度差超过 1，就向上传递失衡标记。
推荐代码
推荐解法：自底向上+递归法
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： 递归返回子树高度；一旦发现某个节点左右高度差超过 1，就向上传递失衡标记。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用自底向上递归，在返回高度的同时判断是否失衡。
核心过程
- 递归获取左右子树高度。
- 若某一侧已经失衡，就直接向上返回失衡标记。
- 若当前节点左右高度差超过 1，也返回失衡。
- 否则返回当前子树高度，最终看根节点是否失衡即可。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)。
面试补一句：这题最关键的优化，是“不要把算高度和判平衡分成两遍做”。
核心思路
平衡二叉树的重点是不要每个节点都重复计算子树高度。自底向上递归可以在算高度的同时顺手判断是否失衡。
步骤讲解
1
递归获取左右子树高度
先递归拿到左右子树的高度结果。
为什么这样做：当前节点是否平衡完全依赖左右子树高度。
对应代码提示：int left = height(node.left); int right = height(node.right);
2
当前层判断是否失衡
若左右高度差大于 1，直接返回特殊值表示失衡。
为什么这样做：一旦某层失衡，整棵树就不可能平衡。
对应代码提示：if (Math.abs(left - right) > 1) return -1;
3
平衡时返回当前高度
若当前层平衡，则返回 max(left, right) + 1。
为什么这样做：父节点还需要利用当前子树高度继续判断。
对应代码提示：return Math.max(left, right) + 1;
易错点
每个节点都单独算高度
会把复杂度推到 O(n^2)。
正确理解：用自底向上递归，把高度计算和失衡判断合并。
发现子树失衡还继续算
浪费计算，也让逻辑变绕。
正确理解：用特殊返回值直接向上传播失衡状态。
把“平衡”理解成左右高度相等
题目要求的是高度差不超过 1。
正确理解：判断条件是
<= 1，不是必须相等。复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比自顶向下反复算高度更高效。
适用判断：树题若需要同时维护“子树属性 + 是否满足约束”，优先考虑自底向上递归。
额外提醒
- 递归返回值既可以是高度，也可以顺便携带失衡标记。
动画演示
如果你还没完全看懂，可以展开动画演示。
自底向上+递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
自底向上+递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树的JSON格式，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。