京公网安备11010502063487号给定一棵二叉树，判断它是否是高度平衡的：树中每一个结点的左右两棵子树的高度差都不超过 1，不只是根结点。一个常见陷阱是只检查根这一层——算出根的左右子树高度，差不超过 1 就直接判定平衡，完全不管子树内部是否也满足这个条件。本文用真实反例和 30000 组随机树验证，13% 的树会被这种写法误判为平衡，再给出正确的 O(n) 自底向上写法、5 种语言实现，以及逐层短路判断的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵二叉树，判断它是否是高度平衡的：本题定义为——树中每一个结点的左右两棵子树的高度差都不超过 1（不只是根结点，是"每一个"结点）。一共 5 组用例，覆盖：官方两个示例、空树、单结点、一条不平衡的链：
[3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
题目定义里最容易被漏看的一个词是"每一个结点"。一个常见的简化写法只检查根这一层：算出根的左子树高度和右子树高度，只要两者差不超过 1 就直接判定"平衡"，完全不管左右子树内部自己是不是也满足这个条件。构造一个反例：根的左右子树高度都是 4（差为 0，根这一层看起来完全没问题），但左子树内部有一个结点自己的左右两边高度差达到了 2：
构造的树：root.left 高度=4，root.right 高度=4（根这一层差为 0）\n正确写法（递归检查每一个结点） → false\n陷阱写法（只看根这一层的高度差） → true
为了确认这不是个例，做了一次随机测试：生成 30,000 棵随机二叉树（结点数 0 到 15）：
30,000 组随机树：\n陷阱写法误判为平衡（实际不平衡） 3,894 组，占 13.0%\n陷阱写法误判为不平衡（实际平衡） 0 组
13% 的随机树会被这种写法误判成平衡，而且这种写法从来没有反过来把真正平衡的树判断成不平衡——它只检查了"平衡"这个要求在根这一个位置的表现，却把"每一个结点都要满足"这个范围条件直接丢掉了。这道题的定义本质上是一个递归定义，不能只检查最外层。
自底向上、一次遍历同时完成"求高度"和"判断平衡"：helper(node) 正常情况下返回这个结点的高度；一旦发现某个结点的左右子树高度差超过 1，或者左右子树里已经有更深的地方不平衡（用 -1 表示），就直接返回 -1 并逐层短路上传，不再继续计算无意义的高度。时间 O(n)（每个结点只访问一次），空间是递归深度 O(h)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def is_balanced(root): def helper(node): if node is None: return 0 lh = helper(node.left) if lh == -1: return -1 rh = helper(node.right) if rh == -1: return -1 if abs(lh - rh) > 1: # 这个结点自己就不平衡，提前短路 return -1 return 1 + max(lh, rh) return helper(root) != -1
$ python3 solution.py [3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
Java · 解法代码class Solution { public boolean isBalanced(TreeNode root) { return helper(root) != -1; } private int helper(TreeNode node) { if (node == null) return 0; int lh = helper(node.left); if (lh == -1) return -1; int rh = helper(node.right); if (rh == -1) return -1; if (Math.abs(lh - rh) > 1) return -1; // 这个结点自己就不平衡，提前短路 return 1 + Math.max(lh, rh); } }
$ javac -d build Main.java && java -cp build Main [3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
Go · 解法代码func isBalanced(root *TreeNode) bool { var helper func(node *TreeNode) int helper = func(node *TreeNode) int { if node == nil { return 0 } lh := helper(node.Left) if lh == -1 { return -1 } rh := helper(node.Right) if rh == -1 { return -1 } diff := lh - rh if diff < 0 { diff = -diff } if diff > 1 { // 这个结点自己就不平衡，提前短路 return -1 } if lh > rh { return lh + 1 } return rh + 1 } return helper(root) != -1 }
$ go run solution.go [3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
JavaScript · 解法代码function isBalanced(root) { function helper(node) { if (node === null) return 0; const lh = helper(node.left); if (lh === -1) return -1; const rh = helper(node.right); if (rh === -1) return -1; if (Math.abs(lh - rh) > 1) return -1; // 这个结点自己就不平衡，提前短路 return 1 + Math.max(lh, rh); } return helper(root) !== -1; }
$ node run.js [3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
C++ · 解法代码class Solution { public: bool isBalanced(TreeNode* root) { return helper(root) != -1; } private: int helper(TreeNode* node) { if (!node) return 0; int lh = helper(node->left); if (lh == -1) return -1; int rh = helper(node->right); if (rh == -1) return -1; if (abs(lh - rh) > 1) return -1; // 这个结点自己就不平衡，提前短路 return 1 + max(lh, rh); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [3,9,20,null,null,15,7] → true [1,2,2,3,3,null,null,4,4] → false [] → true [1] → true [1,2,null,3,null,4] → false
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的 O(n) 自底向上实现另外和一个更直接、但是 O(n²) 的写法（对每个结点都独立重新计算一次左右子树高度）做了随机对拍：
随机对拍 30,000 组（结点数 0 到 15 的随机二叉树），O(n) 自底向上版与 O(n²) 逐结点重算版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [3,9,20,null,null,15,7]：递归从根展开，先算左子树高度，再算右子树高度，每一步都检查当前结点的左右高度差有没有超过 1；只要发现某处超过 1（或者子树里已经报告了不平衡），就整体短路返回 -1，不再白算后面的高度。蓝色是正在展开的结点，绿色是已经求出高度且判定平衡的结点，黄色是发现不平衡、正在短路返回的结点（这个示例最终没有触发短路）。每一帧都是把上面的解法在这组输入上真实执行记录下来的。