刷 LeetCode 的朋友应该对这道题不陌生LeetCode 111 Minimum Depth of Binary Tree 属于二叉树入门级别的题目但说实话它坑过的人远比想象中多。我见过不少能轻松写出最大深度的人在这道题上交出第一版代码之后直接被 WA卡住的点几乎都是同一个没有想清楚“最小深度”和“最大深度”在递归上的本质区别。这道题非常适合用来检验你对二叉树递归的理解是否扎实也很适合拿来练 BFS 的层序思维。无论你是刚开始刷题、准备面试还是想系统过一遍二叉树经典题这道题都值得认真复盘一次。1. 先搞懂最小深度到底怎么算两个定义级陷阱1.1 叶子节点的判断决定了整个递归逻辑先看 LeetCode 的官方定义最小深度是从根节点到最近叶子节点的最短路径上的节点数量。这里面的关键词不是“最小”而是“叶子节点”。叶子节点指没有子节点的节点不是“某个节点没有左孩子就算叶子”也不是“某一层最先出现的节点”。很多错误的递归解法本质上就是把叶子节点的判断搞错了。比如一棵树长这样1 / \ 2 3 / \ 4 51 是根2 和 3 有孩子4 和 5 没有孩子。叶子节点是 4 和 5所以最短路径是 1 - 2 - 4路径上有 3 个节点最小深度是 3。这个例子很简单但真正容易出错的是单子树的情况。比如一棵树只有一个左孩子链1 / 2 / 3根节点 1 没有右孩子。如果按“最大深度的模板”直接取左右子树的最小值会得到min(0, 2) 1 1。但 1 不是叶子节点它的路径必须往下走到 3 才算结束正确答案是 3。这就是第一个定义级陷阱根节点没有右孩子不代表最短路径可以停在根节点因为根节点自己不是叶子。1.2 千万别把“不存在的一边”当成“深度 0”很多第一次写这道题的人递归体是这么写的def minDepth(root): if not root: return 0 return min(minDepth(root.left), minDepth(root.right)) 1这个版本对应最大深度是完全没有问题的因为最大深度求的是“最远能走到哪”空子树返回 0往上加 1 就能算出树的高度。但最小深度不能这么玩原因很简单空子树代表的是“这条路不存在”而不是“这条路深度为 0 并且已经到达叶子”。我把这个坑换成一个生活化的类比你在一个地下迷宫里找最近的出口有一条路走到底发现是死胡同另一条路还没探索。你不能因为死胡同离你近就直接说“最近的出口就在那个死胡同里”。死胡同代表“没有出口”必须走到真正有出口的那条路上去看距离。空子树就是那个死胡同它不是深度为 0 的叶子而是“此路不通”。所以在递归处理时如果某个节点只有一个孩子深度计算必须往存在的那个孩子方向走而不是直接把不存在的那个孩子当作 0 参与比较。1.3 从三个具体例子反推递归关系我习惯在写递归之前先在草稿上推两个例子确保递归关系是对的。第一个例子空树。null没有根节点路径都不存在最小深度就是 0。这是题目约定也对应递归的终止条件。第二个例子只有一个根节点。1根节点就是叶子节点路径只有它自己节点数量是 1所以最小深度是 1。第三个例子根节点只有左孩子。1 / 2根节点 1 不是叶子path 必须往下走到节点 2 才结束所以最小深度是 2。把这三个例子放到递归框架里看可以总结出这样一套逻辑当前节点为空返回 0。当前节点左子树为空右子树不为空最小深度只可能来自右子树答案是minDepth(right) 1。当前节点右子树为空左子树不为空最小深度只可能来自左子树答案是minDepth(left) 1。左右子树都不为空答案才是min(minDepth(left), minDepth(right)) 1。这套逻辑是几个版本代码的共同内核后面写的每一版递归本质上都是在对这个逻辑做不同形式的表达。2. 递归解法DFS 三种写法的思路对比与代码选择2.1 最稳的写法先判空再一一分支如果希望代码一看就懂、review 的时候不用解释我最推荐这一版def minDepth(self, root: TreeNode) - int: if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return self.minDepth(root.right) 1 if not root.right: return self.minDepth(root.left) 1 return min(self.minDepth(root.left), self.minDepth(root.right)) 1这段代码把情况拆成四种空节点、叶子节点、只有右子树、只有左子树、两边都有。每一步都对应“当前节点是不是叶子”“最短路径应该往哪走”的直观判断不容易出错。在纸上推一遍上面那个单链例子1 / 2 / 3调用minDepth(1)时root 非空不是叶子左孩子存在右孩子为空所以进入not root.right分支返回minDepth(2) 1。minDepth(2)继续走同样的分支变为minDepth(3) 1。minDepth(3)左右孩子都为空返回 1。逐层往上带最后得到 3。整个过程很清晰。2.2 面试里常用的 min/max 技巧写法另一种非常常见的写法是利用max来处理单子树情况很多人第一次看到会觉得很巧妙但其实它只是把上一版的分支合并了def minDepth(self, root: TreeNode) - int: if not root: return 0 left self.minDepth(root.left) right self.minDepth(root.right) if not root.left or not root.right: return max(left, right) 1 return min(left, right) 1这里的核心洞察是对于只有一个孩子的节点整个子树还没走到叶子所以不能取空子树那一侧的最小值只能走存在的孩子也就是两个递归结果里更大的那一个。max(left, right)在这时候就是“非空子树的方向”。不过要提醒一句这种写法对“刚接触二叉树递归”的人来说不是那么直观。面试时如果用了这版一定要能讲清楚为什么max在这里是合理的否则面试官一问就可能露怯。我自己更推荐把第一种写法的分支逻辑讲明白代码用哪种其实都可以。还有一小撮人会写一个用 INF一个很大的数做占位的版本def minDepth(self, root: TreeNode) - int: if not root: return 0 if not root.left and not root.right: return 1 ans 10 ** 9 if root.left: ans min(ans, self.minDepth(root.left) 1) if root.right: ans min(ans, self.minDepth(root.right) 1) return ans这个版本把“只有一边子树”的问题转化为“只递归存在的边另一边不进入计算”思路也很干净但要注意初始值要足够大而且本质上它比前两个版本多了一层叶子判断在 LeetCode 上跑起来差别不大面试时看个人习惯。2.3 递归的深度代价与栈溢出问题聊递归写法的时候经常有人问这题用递归会不会栈溢出二叉树的递归深度等于树的高度。最坏情况下树退化成一条链比如每个节点都只有左孩子那么节点数量是 n 的时候递归深度也是 n。Python 的默认递归深度限制通常在 1000 左右如果给一棵一万个节点的单链树递归版本直接就会抛出 RecursionError。LeetCode 的测试用例一般不会到这种极端程度但你在本地自测时完全可能遇到。所以面试被问到“递归有什么缺点”时不要只说“写起来简单”要能接上“递归深度受调用栈限制极端退化树可能溢出工程上更倾向于用显式的栈或 BFS”。能说出这一层说明你对递归的理解不是背代码而是真知道它的边界在哪。3. BFS 层序遍历为什么它是这道题的效率最优解3.1 层序遍历与最小深度的天然匹配这道题用 DFS 能做但如果你去翻 LeetCode 的 Discuss 区会发现时间更优的解法大多是 BFS。原因其实很简单BFS 天然就是一层一层往下扫第一次遇到叶子节点的时候当前层数就是最小深度可以立即返回不需要把整棵树走完。还是拿找钥匙做类比你在一个多层建筑里找一层楼里藏着的保险箱钥匙DFS 是拿着手电筒把第一层某个房间全部翻完之后再下到第二层BFS 则是每层每层地排查先看第一层所有房间再看第二层所有房间。如果钥匙藏在很浅的位置BFS 明显更早找到。最小深度本质上是“离根最近的叶子在哪一层”这和 BFS 的搜索顺序完全一致。3.2 Python 层序实现遇到第一个叶子直接返回BFS 的实现思路是使用队列逐层保存节点每处理完一层就把深度加 1直到遇到某个节点左右孩子都为空直接返回当前深度。from collections import deque def minDepth(self, root: TreeNode) - int: if not root: return 0 q deque([root]) depth 1 while q: for _ in range(len(q)): node q.popleft() if not node.left and not node.right: return depth if node.left: q.append(node.left) if node.right: q.append(node.right) depth 1 return depth这套代码的关键点有两个。第一for _ in range(len(q))这一行的含义是“只处理当前这一层的节点”因为在循环之前我已经取到了这一层的节点数量循环过程中新加入队列的孩子节点不会被本次循环处理而是留到下一层。这个技巧是层序遍历的标配一定要理解熟。第二遇到叶子节点时return depth注意 depth 在最外层循环开始时是 1每处理完一层才加 1。例如根节点本身就既是根又是叶子时进入循环后第一次 popleft 就发现left和right都是空直接返回 1处理得非常干净。如果用 Java 写代码风格也差不多public int minDepth(TreeNode root) { if (root null) return 0; QueueTreeNode queue new LinkedList(); queue.offer(root); int depth 1; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { TreeNode node queue.poll(); if (node.left null node.right null) { return depth; } if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } depth; } return depth; }3.3 BFS 和 DFS 到底怎么选一张表讲清有些人会有疑问BFS 代码比递归长为什么还要用它来看这张对照表答案就很清楚了维度递归 DFS层序 BFS平均时间需要遍历整棵树才能确定最小值遇到第一个叶子就返回通常更快最坏时间O(n)O(n)空间极端情况下递归栈 O(n)队列最多存一层的节点极端二叉树最坏也是 O(n)代码长度短但分支易错略长但逻辑直观对树结构的要求递归深度受限制无递归深度问题从“找最近叶子”这个任务来看BFS 更符合直觉而且在树很“高”但“叶子出现在浅层”时性能优势明显。DFS 的优势在于代码简洁、不需要额外数据结构在树比较平衡或者题目只要求返回结果不要求最优路径时写起来更顺手。面试时如果时间充裕我建议先给 DFS 的递归版本再补一句“其实这题用 BFS 更好因为最早遇到的叶子就是答案”然后顺手把 BFS 写出来。这会让面试官看到你不是只背模板而是懂怎么根据题目特征选算法。4. 面试官喜欢怎么扩展最大深度、N 叉树与变体4.1 最大深度 vs 最小深度只差一个字代码差很多最大深度对应 LeetCode 104 Maximum Depth of Binary Tree几乎人人都会写def maxDepth(self, root: TreeNode) - int: if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) 1最小深度不能直接套用原因前面已经说过空分支不被视为叶子。所以两个题目的核心差异在于“空节点如何参与计算”。最大深度里空节点的 0 是合理的“走到底”可以直接参与比较最小深度里空节点代表的“无路径”不能参与比较。这里有个有意思的测试组合一个完全二叉树最大深度和最小深度相等。一个单链树最大深度是 n最小深度也是 n。一个根节点有左子树很深、右子树为空的树最大深度取决于深的那一边最小深度也取决于深的那一边。分析到这你会发现最小深度的真正难点只在“单子树节点”的处理上其他场景和最大深度很像。4.2 N 叉树版本children 列表怎么处理LeetCode 还有一道 N 叉树的最大深度题但最小深度同样可以自己扩展。N 叉树的节点定义不再是 left/right 两个指针而是一个 children 列表。def minDepth(self, root: Node) - int: if not root: return 0 if not root.children: return 1 return min(self.minDepth(child) for child in root.children) 1如果某个节点是叶子即 children 为空说明路径到此结束返回 1。否则就遍历所有孩子取最小值加 1。这里能直接“无脑取 min”因为不存在的孩子根本不会出现在 children 列表里不会出现二叉树那种“空指针被当成 0 参与比较”的问题。这也是为什么 N 叉树版本反而比二叉树版本更好写。用队列写 N 叉树的 BFS 也很自然只需要把“判断 left/right 是否存在”改成“遍历 children”。这个变体在面试里如果被问到可以直接顺着二叉树的 BFS 思路改难度不大。4.3 延伸到工程场景最小深度的实际含义这道题看起来非常学术但“从起点到最近满足条件的节点”这个模型在工程里很常见。比如后端做服务依赖的“最短调用链”分析时要寻找离当前服务最近的故障叶子节点本质上就是一个从根节点开始的 BFS遇到第一个状态异常的节点就停止。再比如决策树的剪枝要判断从根节点到最近叶子节点的距离来决定是否需要合并子树其实也和这道题同构。刷题的时候如果能多问一句“这个模型的现实场景是什么”对算法思维的养成会很有帮助。LeetCode 上的很多题都不是纯粹的脑筋急转弯而是把现实问题抽象成了树或图上的搜索问题。5. 从 WA 到一次 AC边界测试与调试建议5.1 提交前先列四个必测用例不管用什么写法我建议提交之前先把下面几类用例在本地或编辑器的示例测试里跑一遍测试用例期望结果为什么测它[]0空树边界[1]1根节点就是叶子[1,2]2根节点只有左孩子最容易触发错误分支[3,9,20,null,null,15,7]2正常的多层树验证常规逻辑很多人在[1,2]上会栽跟头。如果你写的是“无脑 min”版本会返回 1而正确答案是 2。把这个用例背下来基本就能挡住一多半的错误写法。5.2 我踩过的两个坑空指针当零、深度从 1 还是 0我第一次写这道题时用的是递归第一版代码def minDepth(self, root: TreeNode) - int: if not root: return 0 return min(self.minDepth(root.left), self.minDepth(root.right)) 1提交之后在[1,2]上直接 WA。当时很困惑因为最大深度代码明明是这么写的。后来仔细检查才意识到我把“空子树”和“深度为 0 的路径”混为一谈了。空子树不是一条合法的路径结尾因为空子树没有叶子节点。这个问题很容易被忽视因为你对着代码看的时候逻辑上会觉得“min(0, 1) 1 1 很合理”但树的结构规定了根节点不能作为叶子直接结束。第二个坑是深度的起点。LeetCode 定义的最小深度返回的是“节点数量”所以根节点的深度是 1不是 0。如果写 BFS 时把初始 depth 设成 0会导致最终的答案比预期少 1。做二叉树题目之前先确认题目定义的是“路径上的节点数”还是“边的数量”这决定了返回值要不要加 1。LeetCode 大多数二叉树题用的是节点数但不同 OJ 或面试官可能约定不同最好提前问清楚。5.3 实用调试技巧打印树 自定义测试写递归题时如果只在脑子里推演很容易在层数比较多的时候转晕。我常用的一个办法是写一个简单的辅助函数把树的前序遍历或层序遍历打出来先确认树的结构符合预期再去看递归结果。比如在本地调试时快速构造一棵树并打印层序from collections import deque def build_tree_from_list(values): if not values: return None root TreeNode(values[0]) q deque([root]) idx 1 while q and idx len(values): node q.popleft() if idx len(values) and values[idx] is not None: node.left TreeNode(values[idx]) q.append(node.left) idx 1 if idx len(values) and values[idx] is not None: node.right TreeNode(values[idx]) q.append(node.right) idx 1 return root def print_tree(root): if not root: return q deque([root]) while q: node q.popleft() print(node.val if node else None, end ) if node: q.append(node.left) q.append(node.right) print() root build_tree_from_list([3, 9, 20, None, None, 15, 7]) print_tree(root)LeetCode 网页版自带“自定义测试用例”功能可以直接输入层序序列化后的数组不用自己造辅助函数。本地练习时上面这种 build 工具函数会经常用到建议写一次然后收藏起来后续二叉树题都会用得上。5.4 一个通用的二叉树递归模板最后分享一个我自己用下来很顺手的二叉树递归模板其实也是从这道题总结出来的1. 写终止条件空节点返回什么 2. 判断当前节点是不是叶子是叶子就返回什么 3. 根据题目要求 - 找最大深度 - 无脑 max(left, right) 1 - 找最小深度 - 左右子树有一边为空时走非空那边 4. 递归调用左子树和右子树 5. 合并结果这道题对应到模板里最关键的是第 3 步和第 5 步。能在写代码之前把这两个问题想清楚比背任何现成代码都有效。对于面试来说讲清楚自己的推导过程比直接甩出一个标准答案更能反映真实水平。每次做二叉树题碰到那些“看起来很简单、一提交就出错”的题我都会想起 LeetCode 111 这道题。它看起来只是最大深度的镜像题实际却是对“叶子节点”和“空子树”这两个基本概念的最好检验。把这道题吃透后面再做路径总和、二叉树最近公共祖先这类题目你会明显感觉到一些共通的东西开始浮现。