如果你也在跟代码随想录的节奏刷二叉树Day17 这三道题大概率已经迎面撞上了111. 二叉树的最小深度、222. 完全二叉树的节点个数、110. 平衡二叉树。这三道题单个拎出来都不算难但放在同一天处理恰好能帮你把二叉树递归的两个关键层面一次打通一是每一步递归到底该返回什么值二是递归结构的设计如何影响时间与空间复杂度。这篇文章就把三题的思路、代码实现、易错点以及我踩过的调试坑完整讲一遍希望能让正在刷题的朋友少走点弯路。1. 三个经典题为什么被排在同一天1.1 共同基因本质都是递归遍历框架的变体代码随想录在讲完二叉树的基础遍历前中后序、层序之后马上安排这三个题是有意为之的。细看你会发现这三个题的解题骨架完全一致递归函数接收一个节点返回值要么是深度、要么是节点个数、要么是平衡状态与高度。它们都不需要修改树结构只是从树里读出信息所以核心就两个问题递归的终止条件是什么每层递归向上返回什么。很多初学者把这三题当成不同类型的题去背解法这是错误的学习方式。正确做法是把它们看成同一个递归模板下的三种返回值设计最小深度返回的是当前子树的最小深度值本质是个整数每层做一次筛选。节点个数返回的是当前子树的节点总数本质是个整数每层做一次累加。平衡二叉树返回的是当前子树是否平衡 当前子树高度本质是个复合状态。你会发现只要你把递归函数的返回值和拿到左右子树返回值之后做什么想清楚这三道题就是同一个套路里的三个变体。这也是刷二叉树题最核心的能力而不是靠背诵题解。1.2 从遍历模板到状态判定的难度递进我还想强调一个容易被忽略的点这三个题目的难度有明显递进。111 是求深度只需要子树返回一个数值属于最基础的递归应用222 是求个数虽然也是数值但引入了完全二叉树的数学特性属于优化层面的考察110 是状态判定返回值不再是单纯数值而是平衡性 高度的组合属于设计层面的考察。这种递进意味着如果你在 111 上没搞懂递归过程后两个题会更吃力。所以我的建议是不要急着看题解代码先自己在纸上写出递归函数定义、终止条件、单层逻辑三行字再对照代码。后面每一步我都会给出这三个要素这不只是给 Day17 用的后续所有二叉树题目都需要这种拆解方式。2. 111. 二叉树的最小深度最容易踩中模板坑的题2.1 关于最小深度的定义陷阱先看题目定义最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意叶子节点四个字这是最大的陷阱点。你直觉会以为二叉树的最小深度就是左右子树最小深度取 min 再加 1乍一听没毛病吧但现实是如果一棵树只有左子树而没有右子树比如根节点左孩子是叶子、右孩子为空那么根节点的右子树深度是 0根节点的左子树深度是 1用 min(1, 0) 1 得到 1这显然是错的。根节点到叶子节点的最短路径应该是根 - 左孩子总共 2 个节点。为什么错因为你把空子树当成了深度 0 的合法子树而实际上空子树并不存在叶子节点它不能参与最小深度的比较。本质是定义问题深度必须终止在叶子节点上空指针不是叶子。我把这类问题叫模板惯性错误。刷过最大深度的朋友会特别容易踩坑因为最大深度的解法 max(left, right)1 完全不需要考虑空子树空子树深度 0 天然合理树的高度就是 max(左高, 右高)1就算一边为空也不影响最大值。但最小深度恰恰相反空子树会让 min 的结果失真必须单独处理。2.2 正确的递归解法与关键判断递归写法其实就是在最大深度的基础上补上单边为空情况的判断。# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 left self.minDepth(root.left) right self.minDepth(root.right) # 单边为空的情况只能走另一边 if root.left is None and root.right is not None: return right 1 if root.right is None and root.left is not None: return left 1 # 左右都不为空或都为空叶子节点 return min(left, right) 1这段代码有四个关键点第一空节点返回 0。这是所有二叉树递归的地基不用多说。第二左孩子为空、右孩子不为空时当前节点只有右边一条路能通向叶子最小深度只能从右子树那边算所以是 right 1。第三右孩子为空、左孩子不为空时同理返回 left 1。第四左右孩子都不为空时才用 min(left, right) 1这才符合最小深度的定义因为左右两边都有可行的叶子路径取较近的那个再加上根节点本身。从复杂度看每个节点只访问一次时间复杂度 O(N)空间复杂度 O(H)H 是树的高度。这个写法在代码随想录的框架里叫作后序递归因为你先处理左右子树再处理当前节点。我自己写的时候有一个习惯不把单边为空分支合并成if not root.left or not root.right。合并写法虽然代码短但很容易让人搞混到底哪个子树可选尤其面试紧张时容易手滑。分开写两个 if逻辑更直观调试更方便。迭代做法也可以做用层序遍历遇到第一个叶子节点直接返回当前深度。这个方案理解门槛最低但你会少练一次后序递归的思路所以我建议优先掌握递归法层序作为保底方案。3. 222. 完全二叉树的节点个数普通遍历与特性优化两条路线3.1 所有二叉树通用的暴力统计先来说最朴素的方案不管是完全二叉树还是任意二叉树节点个数都可以直接用递归统计。递归定义就是左子树节点数 右子树节点数 1终止条件是空节点返回 0。任何遍历顺序都行前中后序无所谓因为只需要计数。class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if root is None: return 0 return self.countNodes(root.left) self.countNodes(root.right) 1这段代码 5 行以内搞定而且不会出错。时间复杂度 O(N)空间复杂度 O(H)。对于 222 这道题普通二叉树的用例用这个方法完全可以过。但既然题目叫完全二叉树的节点个数说明题目白送给你一个完全二叉树的限定条件你不去用它就有点亏。因为完全二叉树的形态非常特殊完全可以做到比 O(N) 更快。3.2 利用完全二叉树的 Log²N 解法完全二叉树有一个性质除了最后一层其他层都是满的且最后一层的节点都靠左排列。这意味着对于一个子树来说如果它的左子树最左侧深度等于右子树最左侧深度那么这个子树一定是一棵满二叉树。满二叉树的节点个数可以直接用公式计算不需要一个一个数。满二叉树的节点数公式节点数 2^h - 1其中 h 是这个满二叉树的深度。这里需要特别提醒位运算的坑如果想用移位运算算 2 的 h 次方很多人会写成2 h或2 (h-1)特别容易错。正确写法是1 h。因为1 h等于 2 的 h 次方。我建议不确定时直接用2 ** h简单直观。继续回到解法。递归逻辑设计如下如果当前子树是满二叉树直接公式返回。如果不是满二叉树就递归计算左子树节点数加右子树节点数再加 1。关键是怎么判断满二叉树。对于完全二叉树来说判断方法很简单分别从当前节点的左孩子和右孩子一路向左走到最底层统计两侧走的层数。如果两侧层数一致说明最后一层在这个范围内是铺满的当前子树就是满二叉树如果两侧层数不一致就说明右边还差几个节点不是满二叉树。class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if root is None: return 0 left_depth self.leftMostDepth(root.left) right_depth self.leftMostDepth(root.right) if left_depth right_depth: # 左子树是满二叉树节点数 2^left_depth - 1再加上右子树的递归结果和根节点 return (2 ** left_depth) - 1 self.countNodes(root.right) 1 else: # 右子树是满二叉树深度较小节点数 2^right_depth - 1再加上左子树的递归结果和根节点 return self.countNodes(root.left) (2 ** right_depth) - 1 1 def leftMostDepth(self, node): depth 0 while node: node node.left depth 1 return depth这段代码需要反复推敲因为很容易绕。我先厘清 leftMostDepth 的定义它返回的是从传入节点出发一路向左走到最底层时经过的节点个数。假设传入 root.left返回的是 h那么以 root 为根的子树里左子树是一棵深度为 h 的满二叉树节点数就是 2^h - 1。这里 h 是节点个数不是边数但因为公式2^h - 1中的 h 在满二叉树中同时满足层数高度节点路径数1的各种说法所以仍然成立。我拿一个具体例子走一遍。假设根节点的左右两侧最左深度相同都是 3说明左子树是一棵满二叉树节点数为 2^3 - 1 7。此时右子树不一定满需要递归继续算。返回值是 7左子树节点数 countNodes(右子树) 1根节点。这里没有重复计算的问题因为 7 只包含左子树内部不包含根节点。如果两侧深度不同比如 left_depth3、right_depth2完全二叉树的性质告诉我们右子树一定比左子树矮一层而且右子树一定是满的。此时右边节点数是 2^2 - 1 3左边不是满的需要递归继续算。返回值是 countNodes(左子树) 3 1。这种算法每次递归都有一侧子树直接公式返回不需要继续展开时间复杂度可以降到 O(log² N)N 是节点总数。这个优化在数据量大时优势明显也很考察你对完全二叉树形态的理解。注意网上很多题解在讲这种优化时会说左子树最左深度和右子树最左深度相等则左子树是满的。这句话的严谨表述是在当前子树本身是完全二叉树的前提下才成立。如果不是完全二叉树这个结论不成立所以这个优化只适用于本题的限定场景。4. 110. 平衡二叉树后序遍历的经典应用现场4.1 为什么必须自底向上平衡二叉树的定义是每个节点的左右子树高度差绝对值不超过 1并且左右子树本身也都是平衡二叉树。注意这里有两个条件一个是高度差限制另一个是递归性。很多人只盯着高度差限制忘了每个子树本身也要平衡结果只判断根节点导致错误答案。最直觉的想法是对每个节点算左子树高度和右子树高度看差值然后再递归检查左右子树是否平衡。这就是典型的前序思路。但前序思路有个致命问题计算高度本身就是 O(N) 的递归每个节点都要重新计算一次左右子树高度整体时间复杂度会变成 O(N²)。虽然小数据上不明显但到了链式树这种极端数据直接超时。正确做法是后序遍历自底向上。先递归处理左右子树拿到它们的高度和平衡状态再判断当前节点是否平衡。这样每个节点的高度只计算一次总体复杂度 O(N)。我常说凡是判断当前节点时需要用到子树完整信息的题优先考虑后序因为后序天然把孩子的计算结果留到了当前处理的时刻不用重复计算。4.2 代码实现与复杂度收益代码可以有两种风格一种用特殊值代表不平衡比如返回 -1另一种返回一个 [balanced, height] 复合结构。我先写用特殊值的经典写法class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: return self.getHeight(root) ! -1 def getHeight(self, node): if node is None: return 0 left self.getHeight(node.left) if left -1: return -1 # 左子树已经不平衡提前剪枝 right self.getHeight(node.right) if right -1: return -1 # 右子树已经不平衡提前剪枝 if abs(left - right) 1: return -1 # 当前节点不平衡 return max(left, right) 1这段代码有两个提前剪枝点。第一处左子树高度返回 -1说明左子树已经不平衡不用再递归右子树直接返回 -1。第二处同理。这两个剪枝不仅能提前结束递归还能避免无谓的计算。返回值设计很巧妙大于等于 0 的整数表示以当前节点为根的子树高度-1 表示以当前节点为根的子树不平衡。外层判断只需要看根节点返回是不是 -1代码非常干净。我走一遍递归过程。假设一棵最简单的树根节点 3左孩子 9右孩子为空。getHeight(9) 返回 1getHeight(None) 返回 0两者差值是 1不超过 1所以根节点返回 max(1, 0)1 2。整棵树平衡。再换一棵树根节点左子树高度 3、右子树高度 1差值 2getHeight 返回 -1isBalanced 直接返回 false。这里还有一个细节值得展开为什么不直接用 False 表示不平衡因为如果用布尔值表示平衡状态高度信息会丢失无法在上一层继续判断高度差。所以必须把状态和高度打包成一个返回值或者用元组返回。Python 里用元组更清晰但刷题环境下用 -1 这个特殊值代码更简洁运行效率也更高。面试中我建议用元组版本方便和面试官解释日常刷题用 -1 版本就够。我还想解释为什么前序会退化成 O(N²)。前序的伪代码是判断当前节点是否平衡需要调用 height 递归算两棵子树高度然后递归判断左右子树是否平衡。height 递归本身会访问以当前节点为根的整棵子树而外层递归会对每个节点调用一次 height所以树上每个节点会被 height 访问多次。最坏情况出现在斜树上height 递归的总代价是 N (N-1) ... 1 O(N²)。这正是很多人把平衡树写成递归后仍然超时的原因。5. 写二叉树题目时的运行时错误排查实录5.1 报错一空指针解引用写二叉树程序时为什么总是报运行时错误这个问题几乎每周都有人问。最常见的运行时错误就是空指针解引用C 里表现为 Access ViolationJava 里是 NullPointerExceptionGo 里是 nil pointer dereference。根因几乎都是同一个递归终止条件没写好或者没有判断当前节点是否为空就访问了 .left 和 .right。典型错误一处理最小深度时直接递归 minDepth(root.left) 和 minDepth(root.right)但忘记写if root is None: return 0。当递归走到叶子节点的空孩子时root 已经是 None下一层递归继续访问 root.left当场崩溃。典型错误二判断左右子树是否存在时写错条件。比如在平衡树里写了if node.left is None and node.right is None就直接返回却忘了处理只有一边为空的情况导致单边子树的空指针被当成叶子节点参与高度统计。结果虽然不崩溃但答案错得离谱运行时错误变成逻辑错误更难排查。我的排查经验是看到运行时错误先别慌按顺序自查三处。第一递归入口有没有判空第二递归调用时传入的参数有没有可能是 None第三访问节点属性之前有没有确认节点不为 None这三个问题过一遍十次里有八次能找到源头。5.2 报错二超时与递归爆炸另一个高频报错是 Time Limit Exceeded也就是超时。二叉树题目的超时绝大多数不是因为数据量大而是因为递归设计里有重复计算。上面平衡二叉树的前序解法就是典型例子每个节点都在重复计算子树高度复杂度退化到 O(N²)在 LeetCode 的极端用例下一跑就超时。还有一种情况是递归深度过大导致栈溢出。LeetCode 常见用例里一棵 10^4 层的斜树用递归很容易把函数调用栈打爆。这时候有两个解决方向第一把递归改成迭代用显式栈模拟第二改用层序等天然迭代的写法。不过 LeetCode 对大多数题目的递归深度限制是够用的真正容易栈溢出的场景更多出现在本地调试时默认栈较小。我不建议一开始就换迭代先想清楚递归的复杂度是不是已经是 O(N)如果是 O(N²) 的重复计算优化递归逻辑比换迭代更有效。我本地 debug 时会额外做一个动作限制测试树的规模。如果一上来就构造一个几万节点的树来测就算算法没问题也只是慢看不出是性能问题还是逻辑问题。先用 5 到 7 个节点的小树把结果人工算出来再跑代码对比这样容易定位。5.3 调试二叉树题目的三板斧最后分享三个我实际调试二叉树题目时最顺手的技巧算是自己的独家笔记。第一板斧打印递归返回值。在递归函数里插入打印语句输出当前节点的 val、左右子树返回值以及最终返回值。你会很容易看到哪一层返回了错误值。比如最小深度那题打印出 left 和 right 分别是多少立刻就明白为什么不能无脑 min。第二板斧把树画出来。LeetCode 的 Console 直接用数组表示法比如 [3,9,20,null,null,15,7]但数组和树结构之间还是有差距。我习惯先把它转成树形图或者直接在纸上画出节点和指针。哪个节点的指向错了画出来一眼就能看出来。第三板斧构造边界样例。二叉树很多坑藏在形态上只有右子树、只有左子树、单节点、空树、满二叉树、完全但不满足的二叉树。每道题都要把这些形态全部跑一遍。最小深度那题如果只测一棵对称树根本测不出单边情况节点个数那题如果只测满二叉树也测不出递归分叉是否正确。我还想提一个很多新手容易忽略的细节LeetCode 输入的二叉树是数组表示法例如 [3,9,20,null,null,15,7]很多人在本地构造测试树时习惯手动 new 节点一两个节点还好多了特别容易写错。建议学会写一个数组转二叉树工具函数把所有测试用例都通过数组驱动调试效率会高很多。这个工具函数我放在下面当成一个可以直接拿走的小福利from collections import deque def build_tree(values): if not values or values[0] is None: return None root TreeNode(values[0]) q deque([root]) i 1 while i len(values): node q.popleft() if i len(values) and values[i] is not None: node.left TreeNode(values[i]) q.append(node.left) i 1 if i len(values) and values[i] is not None: node.right TreeNode(values[i]) q.append(node.right) i 1 return root这段代码的输入就是题目里的数组表示法输出二叉树根节点。用它能帮你把题目用例批量自动化跑起来排查逻辑问题会快很多。对我来说这三道题的训练价值不在于能不能做出来而在于能不能把递归返回值设计、终止条件边界、复杂度优化这些底层能力一次打通。我每次带新人刷二叉树都让他们把这三道题当作一个整体反复练练到随手写出正确代码的程度再往后做路径总和、构造二叉树这类更复杂的题会轻松得多。这是我在实际操作中最真实的体会算法题不像背单词刷过一遍就完事一个递归逻辑是不是真懂了隔三天重新做一次立马见真章。我自己隔段时间重刷这三道题时也会重新发现某个边界条件理解得不够透彻这本来就是成长的正常节奏。