平衡二叉树 图解题解
判断二叉树是否平衡，为什么从底往上算只需走一遍？
检查每层书架是否平衡：从最底层开始往上量高度，量完顺手看两边差没差超过一格。一旦某层失衡就亮红牌往上传，上面每层见到红牌直接也传红牌不再量——这样从叶子到根一趟走完，每个节点的高度只算一次，发现不平衡立刻短路，整体只需 O(n)。
这道题到底在问什么
- 输入
- 根为 1 的二叉树
- 输出
- false
最优解：一步一步想明白
- 3把「失衡」用 -1 编码上抛，就是经典的「剪枝」：一旦确定不平衡，整棵树后续都不用再算了。
- 4后序遍历：先把左子树彻底算完，再右子树，最后才轮到父亲。每个节点会留一条记录：左高、右高、它们的差、以及返回给父亲的高度。
- 5轮到节点 12（橙色）。它是叶子，左右子树都空，左高 = 0、右高 = 0。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 6节点 12 算左右高度差：|0 - 0| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(0, 0) = 1——「1」是它自己这一层，max 取左右里更深的那条链。
- 7轮到节点 8（橙色）。先读它两个孩子已经算好的高度：左高 = 1，右高 = 0（子为空就记 0）。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 8节点 8 算左右高度差：|1 - 0| = 1 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(1, 0) = 2——「1」是它自己这一层，max 取左右里更深的那条链。
- 9轮到节点 9（橙色）。它是叶子，左右子树都空，左高 = 0、右高 = 0。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 10节点 9 算左右高度差：|0 - 0| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(0, 0) = 1——「1」是它自己这一层，max 取左右里更深的那条链。
- 11轮到节点 4（橙色）。先读它两个孩子已经算好的高度：左高 = 2，右高 = 1（子为空就记 0）。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 12节点 4 算左右高度差：|2 - 1| = 1 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(2, 1) = 3——「1」是它自己这一层，max 取左右里更深的那条链。
- 13轮到节点 10（橙色）。它是叶子，左右子树都空，左高 = 0、右高 = 0。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 14节点 10 算左右高度差：|0 - 0| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(0, 0) = 1——「1」是它自己这一层，max 取左右里更深的那条链。
- 15轮到节点 11（橙色）。它是叶子，左右子树都空，左高 = 0、右高 = 0。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 16节点 11 算左右高度差：|0 - 0| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(0, 0) = 1——「1」是它自己这一层，max 取左右里更深的那条链。
- 17轮到节点 5（橙色）。先读它两个孩子已经算好的高度：左高 = 1，右高 = 1（子为空就记 0）。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 18节点 5 算左右高度差：|1 - 1| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(1, 1) = 2——「1」是它自己这一层，max 取左右里更深的那条链。
- 19轮到节点 2（橙色）。先读它两个孩子已经算好的高度：左高 = 3，右高 = 2（子为空就记 0）。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 20节点 2 算左右高度差：|3 - 2| = 1 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(3, 2) = 4——「1」是它自己这一层，max 取左右里更深的那条链。
- 21轮到节点 3（橙色）。它是叶子，左右子树都空，左高 = 0、右高 = 0。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 22节点 3 算左右高度差：|0 - 0| = 0 ≤ 1 ✓ 平衡（转绿）。它返回给父亲的高度 = 1 + max(0, 0) = 1——「1」是它自己这一层，max 取左右里更深的那条链。
- 23轮到节点 1（橙色）。先读它两个孩子已经算好的高度：左高 = 4，右高 = 1（子为空就记 0）。 这两个高度都是孩子在「它们自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
- 24节点 1 算左右高度差：|4 - 1| = 3 > 1 —— 失衡！（转红）这个节点违反了「左右高度差 ≤ 1」，所以它返回特殊值 -1，表示这棵子树已经不平衡。-1 会一路往上抛，整棵树判定为「不平衡」。
⚠️ 容易写错的地方
✗ 错：自顶向下：对每个节点都调用一次 height 再比较
✓ 对：自底向上：一次后序遍历顺手判平衡
自顶向下会把每个节点的高度重复算很多遍，退化成 O(n²)
✗ 错：只检查了根节点的左右高度差
✓ 对：要检查【每一个】节点的左右高度差都 ≤ 1
平衡的定义是对所有节点成立，根平衡不代表子树平衡
✗ 错：发现失衡后还继续算另一侧子树
✓ 对：返回 -1 一路上抛，提前剪枝
已经确定不平衡，再算只是白费时间
完整代码（Python / C++ / Java）
Python
class Solution:
def isBalanced(self, root):
def height(node):
if not node: return 0
L = height(node.left)
if L == -1: return -1 # 左子树已失衡，上抛
R = height(node.right)
if R == -1: return -1 # 右子树已失衡，上抛
if abs(L - R) > 1: return -1 # 本节点失衡
return 1 + max(L, R) # 平衡则返回高度
return height(root) != -1C++
class Solution {
int height(TreeNode* node){
if(!node) return 0;
int L = height(node->left);
if(L == -1) return -1; // 左失衡上抛
int R = height(node->right);
if(R == -1) return -1; // 右失衡上抛
if(abs(L - R) > 1) return -1; // 本节点失衡
return 1 + max(L, R); // 平衡返回高度
}
public:
bool isBalanced(TreeNode* root){
return height(root) != -1;
}
};Java
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
int L = height(node.left);
if (L == -1) return -1; // 左子树已失衡，剪枝上抛
int R = height(node.right);
if (R == -1) return -1; // 右子树已失衡，剪枝上抛
if (Math.abs(L - R) > 1) return -1; // 本节点左右高度差>1，失衡
return 1 + Math.max(L, R); // 平衡则返回高度给父亲
}
}复杂度
时间
O(n)
自底向上每个节点只访问一次；失衡时还能提前剪枝
空间
O(h)
递归栈深度 = 树高 h，最坏（退化成链）O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 平衡二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用后序遍历？+
判断一个节点是否平衡，需要先知道它左右子树的高度，所以必须先算完两个孩子才能算父亲——这正是后序（左→右→根）。
用 -1 表示失衡有没有坑？+
前提是正常高度永远 ≥ 0，-1 不会和合法高度撞车，所以可以安全地把 -1 当「失衡信号」。若高度可能为负则要换别的哨兵值。
这套「递归返回高度、顺手判条件」的套路还能解什么？+
二叉树的直径（LC543）、最大深度（LC104）、最大路径和（LC124）等都同构：一次后序遍历，返回单边信息的同时维护一个全局判断或答案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 平衡二叉树 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。