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 边界用例自测清单刷题的时候最忌讳的就是代码写完一跑示例就过急于提交。我习惯在脑海里先过一组边界用例这道题有四个用例是必测的用例树的形状预期结果空树nulltrue单节点只有一个根节点true满二叉树每一层都填满true单链树每个节点只有一个孩子false除非只有 1-2 个节点空树为什么是 true这是对定义边界条件的经典处理一棵没有节点的树它的左右子树高度都是 0差值 0满足条件而且左右子树也都是空树递归上也成立。这个约定源于形式化定义如果你把空树判为 false反而会不符合常规的递归终止逻辑。单链树的判断也值得注意一个只有根节点和右孩子的树根节点左子树高度 0右子树高度 1差值 1所以它是平衡的。但如果右孩子下面还挂着一个右孩子根节点右子树高度变 2左子树高度 0差值 2就不再平衡。很多人第一次写的时候会想当然以为只要所有节点的孩子数量一致才算平衡这其实是把“满二叉树”和“平衡二叉树”混为一谈了。3.4 递归调试的小技巧如果你在做题时发现自己实现的平衡判断有问题我建议不要盯着屏幕干看而是打印节点访问轨迹。具体做法是在每次调用 height 时打印缩进标记和当前节点值比如def height(node, depth0): if not node: print( * depth None - 0) return 0 print( * depth fNode {node.val}) left height(node.left, depth 1) if left -1: print( * depth fNode {node.val} left unbalanced) return -1 right height(node.right, depth 1) if right -1: print( * depth fNode {node.val} right unbalanced) return -1 if abs(left - right) 1: print( * depth fNode {node.val} diff {left} vs {right}) return -1 res max(left, right) 1 print( * depth fNode {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% 的边界错误。这个习惯我保持了很久省下的调试时间远远大于训练样例耗掉的时间。希望这一篇对你有帮助也欢迎你有自己的心得体会时找我交流。 
长河君 · 2026/9/10 8:15:31 · 阅读 1.2k LeetCode 110：平衡二叉树的递归后序遍历核心解法与工程启发
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 边界用例自测清单刷题的时候最忌讳的就是代码写完一跑示例就过急于提交。我习惯在脑海里先过一组边界用例这道题有四个用例是必测的用例树的形状预期结果空树nulltrue单节点只有一个根节点true满二叉树每一层都填满true单链树每个节点只有一个孩子false除非只有 1-2 个节点空树为什么是 true这是对定义边界条件的经典处理一棵没有节点的树它的左右子树高度都是 0差值 0满足条件而且左右子树也都是空树递归上也成立。这个约定源于形式化定义如果你把空树判为 false反而会不符合常规的递归终止逻辑。单链树的判断也值得注意一个只有根节点和右孩子的树根节点左子树高度 0右子树高度 1差值 1所以它是平衡的。但如果右孩子下面还挂着一个右孩子根节点右子树高度变 2左子树高度 0差值 2就不再平衡。很多人第一次写的时候会想当然以为只要所有节点的孩子数量一致才算平衡这其实是把“满二叉树”和“平衡二叉树”混为一谈了。3.4 递归调试的小技巧如果你在做题时发现自己实现的平衡判断有问题我建议不要盯着屏幕干看而是打印节点访问轨迹。具体做法是在每次调用 height 时打印缩进标记和当前节点值比如def height(node, depth0): if not node: print( * depth None - 0) return 0 print( * depth fNode {node.val}) left height(node.left, depth 1) if left -1: print( * depth fNode {node.val} left unbalanced) return -1 right height(node.right, depth 1) if right -1: print( * depth fNode {node.val} right unbalanced) return -1 if abs(left - right) 1: print( * depth fNode {node.val} diff {left} vs {right}) return -1 res max(left, right) 1 print( * depth fNode {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% 的边界错误。这个习惯我保持了很久省下的调试时间远远大于训练样例耗掉的时间。希望这一篇对你有帮助也欢迎你有自己的心得体会时找我交流。