LeetCode 110简单二叉树 · 后序
平衡二叉树 图解题解
判断二叉树是否平衡，为什么从底往上算只需走一遍？
检查每层书架是否平衡：从最底层开始往上量高度，量完顺手看两边差没差超过一格。一旦某层失衡就亮红牌往上传，上面每层见到红牌直接也传红牌不再量——这样从叶子到根一趟走完，每个节点的高度只算一次，发现不平衡立刻短路，整体只需 O(n)。
这道题到底在问什么
判断一棵树是否高度平衡：任意节点左右子树高度差不超过 1。
- root
- [3,9,20,null,null,15,7]
- 输出
- true
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合二叉树 · 后序。
- 4判断是否平衡：每个节点的左右子树高度差都要 ≤ 1。用后序遍历自底向上算高度，顺手查平衡。
- 5先到最底层：叶子 9、15、7 的高度都是 1。
- 6节点 20：左(15)高 1、右(7)高 1，差 |1−1|=0 ≤ 1 平衡 → 高度 = 1+max(1,1) = 2。
- 7根 3：左(9)高 1、右(20)高 2，差 |1−2|=1 ≤ 1 平衡 → 高度 3。
- 8关键帧：后序让每个节点一次算高度 + 顺手查平衡。一旦某子树不平衡就返回 -1 短路，父节点见到 -1 直接也返 -1，不重复算高度 → O(n)。根没返 -1 → 整树平衡 (true)。
- 9反例：这棵树根 1 的左子树高 2、右子树高 0，差 |2−0|=2 ＞ 1 → 不平衡，height 返回 -1 一路短路到根 → false。
- 12把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：每个节点重复求高度
✓ 对：后序一次返回高度并顺手判平衡
重复求会退化到 O(n²)
✗ 错：自顶向下、每个点重新算高度
✓ 对：自底向上后序，一次返回高度
自顶向下对每个节点都算一遍高度 → O(n²)；后序自底向上 O(n)。
✗ 错：height 和 isBalanced 分两次遍历
✓ 对：合并：height 返回 -1 即表示不平衡
分开会重复遍历；用 -1 哨兵一次搞定。
完整代码（Python / C++ / Java）
Python
class Solution:
def isBalanced(self, root):
def height(node):
if not node: return 0
left = height(node.left)
if left == -1: return -1 # 左已不平衡，短路
right = height(node.right)
if right == -1: return -1
if abs(left - right) > 1: return -1 # 当前不平衡
return max(left, right) + 1
return height(root) != -1C++
class Solution {
public:
int height(TreeNode* node) {
if (!node) return 0;
int left = height(node->left);
if (left == -1) return -1;
int right = height(node->right);
if (right == -1) return -1;
if (abs(left - right) > 1) return -1;
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) { return height(root) != -1; }
};Java
class Solution {
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;
}
public boolean isBalanced(TreeNode root) { return height(root) != -1; }
}套路模板 · 后序高度 + 哨兵
# 平衡判断骨架 · 后序 + (-1)哨兵
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 max(L, R) + 1
return height(root) != -1复杂度
时间复杂度
O(n)
每个核心状态按算法要求处理固定次数
空间复杂度
O(h)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 平衡二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
自顶向下为什么是 O(n²)？+
对每个节点都从头算一次子树高度，高度计算 O(n)，叠加 O(n²)。
自底向上怎么做到 O(n)？+
递归一次返回高度顺便判断；用 -1 表示「这棵子树已不平衡」一路短路上传，每点只算一次。
高度和深度的区别？+
高度从叶往上数、深度从根往下数；本题用高度(子树往上返回)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。