LeetCode 110这道平衡二叉树题目，我愿称它为“树结构入门体检单”。你去看大厂的笔试面试题单，几乎每一份都会把这道题放在二叉树板块的前十题里。它看起来就是判断一棵树是不是平衡的，但真正动手写的时候，你会发现不少人在递归边界、高度计算、剪枝时机上翻车。这篇文章我想用最贴近实战的方式，把这道题的解法逻辑、代码实现、边界情况和扩展点全部拆开讲清楚，如果你正在刷题或者准备面试，这篇应该能帮你一次吃透。
1. 题目拆解：平衡二叉树到底在检查什么
1.1 最容易被忽略的递归定义
先看题目里平衡二叉树的定义：一棵二叉树中，每个节点的左右两个子树的高度差的绝对值不超过 1，且左右两个子树也都是平衡二叉树。
这里的关键是后半句——“左右两个子树也都是平衡二叉树”。这句话决定了你不能只检查根节点左右子树的高度差，你还得递归地检查每个子树内部是否平衡。换句话说，平衡是一个全局性质，不是只看顶层就够的。很多第一次刷这道题的人会把思路停在“求根节点左右子树的最大深度，然后相减看看是否大于1”，这种解法在根节点恰好平衡但子树不平衡时就会漏判。
我想用一个生活化的例子帮助你理解：想象你在管理一个公司的组织架构，要求每个部门经理的左右两个副手带的团队人数差不能超过1人，而且每个副手带的团队内部也要满足同样的规则。你只检查CEO的两个副手团队人数差，显然不够，因为某个副手下面的小组长可能已经带了10个人和2个人，严重失衡。
从数据结构的角度来看，这里还涉及一个高频考点：高度（height）和深度（depth）的区别。深度是从根节点往下数，走到某个节点的边的条数；高度是从叶子节点往上数，某个节点到它下属最远叶子的边的条数。LeetCode 110要求的是“高度差”，所以我们的核心递归函数应该返回以当前节点为根的子树的高度，而不是累计向下的深度。
1.2 自顶向下思路为什么不够优雅
很多人的第一反应是写一个 maxDepth 函数，然后对每个节点都调用一次：
int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } bool isBalanced(TreeNode* root) { if (!root) return true; int leftH = maxDepth(root->left); int rightH = maxDepth(root->right); return abs(leftH - rightH) <= 1 && isBalanced(root->left) && isBalanced(root->right); }这段代码在逻辑上没有任何错误，对于一棵小树它完全能通过，但它的问题在于时间复杂度退化成了 O(n²)。原因很直观：isBalanced 递归访问每个节点时，都会触发一次完整的 maxDepth 递归，而 maxDepth 又会对以当前节点为根的整棵子树进行遍历。上层的每个节点都会重复计算下层子树的高度，大量信息被浪费掉了。
如果树的形状接近一条链，比如一棵树每个节点只有右孩子，那么 maxDepth 本身就要走到底部，isBalanced 每递归一层又会再走一遍，总访问次数形成了一种算术级数的累积，节点一多性能就会非常难看。
2. 核心解法：自底向上的后序遍历 + 高度哨兵
2.1 一次递归同时完成“计算高度”和“判断平衡”
这道题最标准的解法是用自底向上的后序遍历思路，也就是先把左右子树的高度都算出来，再在根节点汇总判断。这样做的好处是每个节点只被访问一次，时间复杂度降到了 O(n)。
核心思路可以描述为三句话：
- 空节点高度为 0，天然平衡。
- 非空节点先递归求左子树高度、右子树高度，如果左右子树都不平衡，当前节点直接返回 -1 标识不平衡。
- 如果左右子树都平衡，再比较两棵子树的高度差，如果绝对值大于 1，返回 -1；否则返回“两者较大高度 + 1”作为当前子树的高度。
这里最大的精妙点在于我们把返回值同时当成了两个用途：非负数代表该子树的高度，-1 代表该子树已经不平衡。通过这个哨兵值，整个递归过程就可以提前终止，不需要额外写一个全局标志位，也不需要写额外的递归函数。
2.2 代码实现：Python 和 C++ 两个版本
我先把 Python 版本贴出来，这是面试时写起来最快的版本：
class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: 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: bool isBalanced(TreeNode* root) { return height(root) != -1; } private: 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; } };如果你愿意，也可以把 -1 替换成一个成员变量或者传引用的标志位，但在我看来哨兵值的写法永远是最简洁的，它把“返回高度”和“告知上层已经不平衡”这两件事合成了一个返回值。这样上层递归拿到 -1 后可以直接返回，省掉了后面所有不必要的递归分支，相当于把剪枝写进了函数签名里。
2.3 为什么 -1 哨兵值设计得这么巧妙
我见过很多初学者在这里有一个疑问：“为什么非要用 -1？我用 false 标志位不行吗？”当然可以，但你会发现如果不用哨兵，你至少需要两个返回值：一个是“是否平衡”的布尔值，一个是“子树高度”的整数。要么你定义一个包含两个字段的结构体，要么你引入一个引用参数，让核心函数的签名变得臃肿。
哨兵值之所以好用，是因为树的高度天然是一个非负整数，最浅的叶子节点高度也至少是 0，所以 -1 永远不会和合法高度冲突。这就保证了你可以在递归返回值里安全地区分“当前子树平衡且高度为 X”和“当前子树已经不平衡”两种状态。
从工程视角看，这个思路很像 API 设计里的错误码约定：200 表示成功，非 2xx 表示失败。你的函数返回值自己就携带了状态信息，调用方不用额外约定一个 out 参数去看状态。写代码的人舒服，读代码的人也不累。
3. 关键细节与复杂度推演
3.1 时间复杂度为什么是 O(n)
我不止一次在面试中遇到候选者能写出正确代码，但被问到“时间复杂度为什么是 O(n)”时支支吾吾。这道题的复杂度证明其实很直白：每个节点在递归过程中只会被访问一次，因为递归是在后序遍历的路径上进行，当前节点的 left 和 right 高度计算分别只发生一次，没有重复扫描，也没有对同一节点的二次进入。
我们可以严谨地这样想：对一棵有 n 个节点的树，height 函数会对每个节点恰好调用一次。对于每个节点，我们只做了常数次操作：判断 left 是否为 -1、判断 right 是否为 -1、计算 abs、调用 max。所以总操作次数是 O(n)。递归过程中每次调用都对应一个栈帧，递归深度在最坏情况下会达到树的高度，如果树退化成一条链表，递归深度就是 n，因此空间复杂度是 O(n)。注意这里的空间复杂度不是平均情况下的 O(log n)，而是最坏情况下的 O(n)，因为题目没有保证这是完全二叉树或平衡树。
3.2 剪枝行为：一旦不平衡，立即短路
哨兵值带来的另一个好处是剪枝：当左子树返回 -1 时，代码根本不会再去递归右子树。这意味着如果一棵树在很浅的层次就出现了不平衡，程序能很快退出，不会继续无意义地扫描下面的所有节点。
这其实和很多算法里的短路求值思维是一致的。比如判断两个链表是否相交、判断一个字符串是否包含子串，一旦找到满足条件或违反条件的点，就应该立刻停止。算法题里很多不必要的性能浪费，都来自“把所有工作都做完再去判断”，而正确的做法是“一旦能下结论就停手”。
我在实际测试中专门构造过一棵“根节点平衡但左子树内部极不平衡”的树，比如根节点左子树高度 10、右子树高度 11，但左子树的某个左孩子下面挂了一条 8 层的链子导致左子树内部其实不平衡。这种情况下，哨兵值写法的程序会在发现不平衡子树的那个节点直接返回 -1，然后每一层递归都拿到 -1，最终整棵树在极少节点被访问的情况下就给出了 false。而自顶向下的 O(n²) 写法会先把所有节点的深度都算一遍，耗时差距非常明显。
3.3 边界用例自测清单
刷题的时候最忌讳的就是代码写完一跑示例就过，急于提交。我习惯在脑海里先过一组边界用例，这道题有四个用例是必测的：
| 用例 | 树的形状 | 预期结果 |
|---|---|---|
| 空树 | null | true |
| 单节点 | 只有一个根节点 | true |
| 满二叉树 | 每一层都填满 | true |
| 单链树 | 每个节点只有一个孩子 | false（除非只有 1-2 个节点） |
空树为什么是 true？这是对定义边界条件的经典处理：一棵没有节点的树，它的左右子树高度都是 0，差值 0，满足条件，而且左右子树也都是空树，递归上也成立。这个约定源于形式化定义，如果你把空树判为 false，反而会不符合常规的递归终止逻辑。
单链树的判断也值得注意：一个只有根节点和右孩子的树，根节点左子树高度 0，右子树高度 1，差值 1，所以它是平衡的。但如果右孩子下面还挂着一个右孩子，根节点右子树高度变 2，左子树高度 0，差值 2，就不再平衡。很多人第一次写的时候会想当然以为只要所有节点的孩子数量一致才算平衡，这其实是把“满二叉树”和“平衡二叉树”混为一谈了。
3.4 递归调试的小技巧
如果你在做题时发现自己实现的平衡判断有问题，我建议不要盯着屏幕干看，而是打印节点访问轨迹。具体做法是在每次调用 height 时打印缩进标记和当前节点值，比如：
def height(node, depth=0): if not node: print(" " * depth + "None -> 0") return 0 print(" " * depth + f"Node {node.val}") left = height(node.left, depth + 1) if left == -1: print(" " * depth + f"Node {node.val} left unbalanced") return -1 right = height(node.right, depth + 1) if right == -1: print(" " * depth + f"Node {node.val} right unbalanced") return -1 if abs(left - right) > 1: print(" " * depth + f"Node {node.val} diff {left} vs {right}") return -1 res = max(left, right) + 1 print(" " * depth + f"Node {node.val} height {res}") return res打印出来的结果本身就是一棵树形结构，能很直观地看到在哪一层、哪个节点触发了不平衡判断。这个方法的适用范围不止这道题，所有二叉树递归题都可以用同样的方式打断点、看递归轨迹。
4. 常见错误与高频面试追问
4.1 为什么不能只用最大深度直接判断
这是面试官最常设置的陷阱之一。有些候选人背了求最大深度的模板，看到这题就把 root 的左右子树最大深度算出来，判断差值是否大于 1，然后直接返回。这种解法能通过题目中一些浅层的示例，但本质上只判断了根节点这一个位置，没有递归检查每一个子树。
直觉上问题在于：整体深度差不超过 1，不代表每个子树内部的高度差不超过 1。举个反例，根节点的右子树是一个高度为 3 的满二叉树，根节点的左子树是一个节点、但它的右子树下面挂着一条长度为 5 的链。这时从根节点看，左子树高度 1，右子树高度 3，差值 2，确实会判 false。但如果我把左子树的链减少到长度 2，根节点左右高度就变成了 1 和 3，差值还是 2，也不平衡。你可能会说“那我再把右子树也改矮一点”，问题在于你总能构造出一种情况：某个子树的内部某个孙子节点和它的兄弟高度差超过 1，但根节点两侧高度恰好都在范围内。
所以正确的判断必须深入到每个子问题层面。这也是“递归定义的问题用递归解法”最典型的体现。
4.2 自顶向下什么时候可以用
虽然 O(n²) 的解法在力扣上也能通过，因为测试数据通常不会卡到极致，但我不建议你在面试时给出这种解法。不过有一种场景是例外：如果题目额外限制了递归层数，或者树的规模非常小，那么自顶向下写起来思路更直白，代码更不容易出错。
我在帮助别人复盘时总结过一个经验：如果你在面试现场写不出后序遍历的解法，那写一个自顶向下的版本也远比卡住不说话要强。你可以先给出一个能通过的解法，然后主动说“这里存在重复计算，我可以优化到 O(n)”，再写一遍后序版本。这样既展示了编码能力，也展示了优化意识。
4.3 面试官爱问的三连追问
追问一：如果树的高度非常大，递归解法会不会爆栈？
会。递归解法的最坏空间复杂度是 O(n)，当树退化成链且 n 达到几十万甚至上百万时，递归栈可能会溢出。比如深度超过 10 万的链表式二叉树，Java 默认栈深度一般是几千到几万层，很容易 StackOverflow。
如果面试官问到这个点，你可以提出用迭代方式改写：先做后序遍历的栈模拟，把每个节点的状态记录下来，或者用 Morris 遍历把空间降到 O(1)，但 Morris 遍历改造高度统计会复杂一些。通常面试到这一步已经超出基础题的范围，你能说出迭代思路就已经够了。
追问二：如果不仅要判断是否平衡，还要返回不平衡的节点，怎么办？
你可以让递归函数不只返回高度或 -1，而是返回一个对象，里面包含“是否平衡”的布尔值、“高度”的整数、“第一个失衡节点”的指针或引用。每次递归发现不平衡时就把节点记录下来。本质上还是同一套递归框架，只是返回值携带的信息变多了。这也是从“判断题”升级到“构造题”的常见套路。
追问三：能否用层序遍历判断平衡？
层序遍历不能直接判断，因为平衡的定义依赖树的高度，而层序遍历只能体现“某一层的节点是否存在”，无法直接返回每个节点为根时左右子树的高度。层序遍历更多用于判断完全二叉树、输出锯齿形层次等场景，和这道题不算匹配。
4.4 工程场景里的平衡二叉树
这块内容虽然不直接影响刷题，但在面试中经常被用来考察候选人是否理解“为什么平衡这么重要”。最常见的应用场景是 AVL 树，它强制每个节点的平衡因子绝对值不超过 1，一旦失衡就通过左旋、右旋、左右双旋、右左双旋四种操作恢复平衡。
AVL 树的调整和这道题用的是同一个“高度差”判断标准。理解了 LeetCode 110 的判断逻辑，你就能理解为什么插入或删除节点后要从叶子向上更新平衡因子，也能理解旋转的触发条件为什么会是“左子树比右子树高 2”或“右子树比左子树高 2”。红黑树虽然不用严格的高度差做约束，但它引入的“黑高”概念本质上也是对路径高度的一种软性限制。可以说，这道题是整个平衡树系列的基础观测站，搞定了它，后面学 AVL、红黑树都会顺畅很多。
5. 工程化思考与扩展延伸
5.1 从“判断平衡”到“维护平衡”
力扣 110 只要求静态判断，但实际工程里，一棵树往往要动态插入删除节点，这就会牵扯到“维护平衡”的问题。AVL 树的做法是在每次插入或删除后，沿着插入路径从下往上更新节点高度，并检查平衡因子。一旦发现某个节点的左右子树高度差超过 1，立即根据失衡类型做旋转。
我发现很多人把“判断平衡”和“旋转调整”当成两座孤岛来学，其实它们的连接点就是 LeetCode 110 里那个高度计算函数。AVL 树的节点里通常会存一个 height 字段，更新时可以用“左右子树 height 较大值加一”来刷新。这和我们这题递归返回值的max(left, right) + 1完全一致。
如果你有兴趣做扩展练习，我建议你在写完 110 之后，紧接着做这几个题：
- 剑指 Offer 55 - II：平衡二叉树，判断逻辑完全一样，适合用来巩固。
- LeetCode 104：二叉树的最大深度，本质上就是 110 的高度计算部分。
- LeetCode 543：二叉树的直径，求任意两个节点间最长路径长度，同样依赖高度信息，但思考方向从“检查差值”变成了“求最大值”。
- LeetCode 110 的一个变体：给定一棵二叉树，求所有不平衡节点中高度最小的那个，这就要在递归里额外记录信息。
- 手动实现一个 AVL 树的插入和删除，把判断逻辑用起来，你会有完全不同的体感。
我觉得把这五个题串起来做一遍，你对二叉树递归框架的理解会提升一个明显的台阶，而不是“背了会忘、刷了没感觉”。
5.2 举一反三：这道题里的通用递归范式
LeetCode 110 表面上只是一道判断题，但它内部的递归结构其实是二叉树后序遍历的“三段式”模板：
- 递归出口：空节点。
- 左右递归：先求左子树信息，再求右子树信息。
- 当前节点逻辑：利用左右子树信息计算当前节点的返回值。
这个模板可以套到非常多题目上：求二叉树直径、判断对称二叉树、找二叉树最近公共祖先、计算二叉树中的最大路径和。几乎每一个需要从叶子向根汇总信息的题，都是这个后序遍历三段式的变体。
我在刷题营里带人的时候经常强调一个观点：不要孤立地刷每一道题，要善于总结“题型模板”。一道题的价值不仅在于它本身会不会做，更在于它能不能帮你打通一类题。110 就是一个典型的“后序遍历信息汇总”题目，你把它吃透了，后面遇到 543、124 这些题会轻松很多。
再往深一层说，这种“返回一个值同时携带两种语义”的设计，也能迁移到很多工程项目里。比如数据处理的任务里，一个解析函数可以返回“是否解析成功”的布尔值和“解析后的数据对象”；再比如批量导入任务里，一个函数可以返回错误码，非零值本身就是错误类型，没有必要再包装一层结构体。合理利用返回值，能极大简化代码分支。
6. 结语：这道题带给我的思考
如果让我总结这道题最值得学习的地方，我会说不是那几行代码本身，而是“什么时候该用自顶向下，什么时候该用自底向上”的判断力。自顶向下直观但往往低效，自底向上需要你多花一点脑筋，但常常能拿到 O(n)。面试的时候，你能在分析完复杂度后主动提出优化方向，这是一个非常加分的亮点。
我个人在实际操作中的体会是，类似这种“判断是否符合某种递归性质”的题目，先画出树的形状，再用具体的小例子去跑一遍递归流程，比空想靠谱得多。尤其是那些带 -1 哨兵的题，你手动模拟几个节点，很快就能理解为什么说“返回 -1 相当于剪枝”。
最后再分享一个小技巧：我每次刷这种二叉树题，都会准备一组固定的小样例，包含空树、单节点、双节点、三节点、左斜树、右斜树、完全二叉树。不管做到什么题，先把这组样例跑一遍，基本能预防 80% 的边界错误。这个习惯我保持了很久，省下的调试时间远远大于训练样例耗掉的时间。希望这一篇对你有帮助，也欢迎你有自己的心得体会时找我交流。
