废话不多说这道题我刷过很多遍也看周围不少同学在第一遍写的时候踩进同一个坑。LeetCode 上“二叉树的最小深度”属于那种看起来很简单、真正动手却发现边界条件一堆的题目它比“求最大深度”多了几个隐藏陷阱也正因为如此它经常出现在面试算法题的第一轮和力扣热题 100 中。这道题的核心是给定一个二叉树找出其最小深度。而最小深度的定义是“从根节点到最近叶子节点的最短路径上的节点数量”。注意这里强调的是“叶子节点”。很多人就是在这里翻了车把最小深度理解成“左右子树中较矮的那条路径”结果碰到只有左子树或者只有右子树的单边树时答案怎么都对不上。这篇文章我会从题目本身的定义开始拆把递归解法和 BFS 层序遍历解法都讲透同时结合我在本地调试和实际面试中遇到的各种报错尤其是写二叉树程序时最常见的“运行时错误”整理出一份能直接拿去用的避坑手册。不管你是刚刷 LeetCode 的初学者还是准备冲刺周赛、面试前复习基础题的老手这篇都值得花十分钟看完。1. 题目对“最小深度”的定义比你想象中更严格1.1 最小深度与最大深度的本质区别先看两个 LeetCode 题目的对比。求二叉树最大深度时你只需要递归地取左右子树深度的最大值再加上根节点这一层。但求最小深度时如果直接对称地把max改成min你会发现某些用例过不去。问题的根源在于null节点到底算不算一条合法路径的终点对于最大深度null节点的高度是 0这是合理的因为最大深度天然会选择那些“非空路径”中更长的一条。但对于最小深度null节点不能简单作为最小值的候选者因为最小深度要求路径必须以“叶子节点”结束。如果一个节点的左子树为空、右子树非空那么从根出发经过这个节点继续往下走的路径绝不能在这里终止。我习惯用一个生活化的类比假设你在一个园区里找“最近的出口”每个房间代表一个节点出口代表叶子节点。如果某个接待室只有右门能继续走、左门是封死的你不能停在接待室里说“已经到了出口”因为接待室本身不是出口。同理在求最小深度时null是一个死胡同但它不代表终点真正的终点必须是左右孩子都为空的节点。1.2 叶子节点的定义决定了边界条件题目里明确写了叶子节点是指没有子节点的节点也就是left nullptr right nullptr。这个定义是整个题目的边界条件核心。很多初学者在写递归时会先判断root nullptr然后返回 0。这个判断本身没错但它只在“整棵树为空”或者“递归访问到某个节点的空孩子”时才会触发。问题在于递归逻辑中如果对“只有一个孩子为空”的情况不做区分直接缩小值就会把空孩子当成深度 0 参与计算最终算出的最小深度比真实值小。真正的边界条件设计应该是空树返回 0这是题目约定的边界情况。当前节点是叶子节点返回 1。当前节点左子树为空递归求右子树的最小深度再加 1。当前节点右子树为空递归求左子树的最小深度再加 1。左右子树都不为空取左右子树最小深度的较小值再加 1。这五条规则少任何一条都会出错。1.3 一个最容易写错的答案直接套用 max 的思路我先给你看一个反面教材这是我见过最多人写的第一版// 错误示例 class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); } };这段代码在下面这个用例上就会挂掉root [1, 2]也就是根节点只有左子树没有右子树。按照题目定义最小深度应该是 2路径 1 - 2。但这段代码计算minDepth(root-right)时返回 0minDepth(root-left)返回 1取min后是 0最终返回 1。答案错误。这种错误本质上是混淆了“最小深度”和“最小高度”。在平衡二叉树或者完全二叉树中两者可能一致但二叉树的结构千变万化一旦出现单侧子树为空的情况就必须单独处理。2. 递归解法把问题交给左右子树去回答2.1 递归公式的推导递归解法的核心思想是一棵树的最小深度一定等于“根节点所在层1”加上“子树中较浅的那一条合法路径的深度”。但这里的“子树中较浅”必须建立在“子树存在”的前提下。所以递归公式应该写成如果root为空返回 0。如果root是叶子节点左右孩子都为空返回 1。如果root-left为空返回1 minDepth(root-right)。因为只有右子树可以继续走深度只能从右子树中获得。如果root-right为空返回1 minDepth(root-left)。如果左右子树都不为空返回1 min(minDepth(root-left), minDepth(root-right))。这个公式本质上是在“所有以叶子节点结尾的路径”中找最短的那条。它不像最大深度那样无脑递归而是需要先判断哪棵子树“没有资格参与最小值比较”。2.2 两种递归写法代码与解释第一种写法是标准后序遍历风格逻辑清晰适合面试时手写class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; // 叶子节点 if (root-left nullptr root-right nullptr) return 1; int leftDepth INT_MAX, rightDepth INT_MAX; if (root-left) leftDepth minDepth(root-left); if (root-right) rightDepth minDepth(root-right); return 1 min(leftDepth, rightDepth); } };在这个写法里我把左右子树的深度初始化为INT_MAX。这样做的好处是如果某棵子树为空那么它的深度不会参与min的比较因为INT_MAX在大多数情况下不会被选中。这种“用极大值占位”的思路在很多需要忽略空分支的递归题里都很实用。第二种写法更简洁利用if分支直接排除空子树class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr) return 1 minDepth(root-right); if (root-right nullptr) return 1 minDepth(root-left); return 1 min(minDepth(root-left), minDepth(root-right)); } };个人更推荐第二种。它的可读性很好而且把 1.2 节里提到的五个边界条件直接映射到代码分支上不容易漏判。而且从执行效率上看它也比第一种少了两个变量初始化的步骤。如果你用 Python 写同样可以遵循这个逻辑class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return 1 self.minDepth(root.right) if not root.right: return 1 self.minDepth(root.left) return 1 min(self.minDepth(root.left), self.minDepth(root.right))2.3 递归的时间和空间复杂度以及栈溢出隐患递归解法的时间复杂度是 O(n)其中 n 是二叉树的节点总数。因为每个节点都会被访问一次。空间复杂度取决于递归调用栈的深度最坏情况下当二叉树退化成一条链例如每个节点只有左孩子时递归深度就是 n所以空间复杂度是 O(n)。在实际刷题时如果树的高度非常大比如上万层递归写法可能触发系统栈溢出。力扣的题目数据通常不会把这个极端情况拉满但面试时最好主动提一句“递归解法在极端退化的链式树上空间复杂度会退化到 O(n)如果对栈深度有要求可以用下面的 BFS 迭代写法。”这也呼应了很多人问的一个问题为什么我写二叉树程序时总是报“运行时错误”很多时候就是递归深度太大导致栈溢出力扣会直接报AddressSanitizer: stack-overflow或者Runtime Error。3. BFS 层序遍历第一个遇到的叶子节点就是答案3.1 为什么 BFS 比 DFS 更适合寻找最小深度如果题目只是“求最小深度”用 DFS递归或手动栈也能做但有一个隐含的问题DFS 会先把一条路径走到头即使这条路径非常长你也得走完才能知道它的深度。而 BFS 是按层扩展的天然具备“逐层推进”的特性一旦在某层遇到第一个叶子节点这个节点所在的层数就是最小深度。这个结论成立的原因很简单BFS 访问节点的顺序是从根开始一层一层向外展开的第一层没有叶子第二层没有叶子直到第 k 层第一次出现叶子那么从根到该叶子的路径长度就是 k而前面 k-1 层没有叶子说明所有路径长度至少是 k所以 k 就是最小深度。用通俗的话说BFS 像“地毯式搜索”一层一层找出口找到即停DFS 像“一条路走到黑”哪怕旁边就有出口你也得先撞墙才能回头。所以在最小深度这类问题中BFS 平均效率更高尤其在树比较矮胖的情况下BFS 可以提前终止不需要遍历整棵树。3.2 BFS 代码实现细节BFS 的实现基于队列核心逻辑是将根节点入队。记录当前深度为 1。循环处理当前队列中的所有节点也就是当前层的所有节点。如果某个节点是叶子节点直接返回当前深度。否则将它的非空孩子节点加入队列。当前层处理完后深度加 1继续下一层。C 代码class Solution { public: int minDepth(TreeNode* root) { if (root nullptr) return 0; queueTreeNode* q; q.push(root); int depth 1; // 根节点本身算一层 while (!q.empty()) { int levelSize q.size(); // 当前层的节点数量 for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); // 遇到第一个叶子节点直接返回 if (node-left nullptr node-right nullptr) { return depth; } if (node-left) q.push(node-left); if (node-right) q.push(node-right); } depth; } return depth; } };Python 代码from collections import deque class Solution: def minDepth(self, root: Optional[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循环之前我先把levelSize q.size()存下来了。这个操作非常关键。如果在for循环中直接用q.size()作为循环结束条件而循环体里又不断向q中push新节点那么q.size()是动态变化的会导致遍历完当前层之后继续遍历下一层的节点深度统计就会出错。类似的坑在“腐烂的橘子”LeetCode 994那道 BFS 题里也会遇到你需要统计的是当前轮次已经“腐烂”的橘子数量如果在循环过程中新腐烂的橘子又加入了队列不提前锁定size轮次就会混乱。3.3 两种解法的对比我把递归解法和 BFS 解法放在一起做了个对比方便你根据场景选择。维度DFS 递归法BFS 迭代法时间复杂度O(n)O(n)但遇到叶子早时提前停止空间复杂度O(h)h 为树高最坏 O(n)O(w)w 为最大层宽度最坏 O(n)是否提前终止不能提前终止需遍历所有路径遇到第一个叶子立即返回极端链式树表现可能栈溢出空间占用较大但稳定代码复杂度短小精悍稍长但思路直观面试时可以这样讲递归解法代码简洁适合快速写出答案BFS 解法在树比较宽、叶子比较浅的情况下效率更高而且天然避免了递归栈溢出的风险。实际做题时如果没特别说明两种解法都能通过力扣的全部测试用例。4. 写二叉树代码常遇到的运行时错误与排查思路4.1 空指针访问最常见的运行时错误我见过很多同学在写二叉树相关代码时报的最多错误就是“运行时错误空指针访问”。典型场景是没有判断root是否为空就直接访问root-left或者在递归中某个节点的某棵子树为空却没有在访问前判断。以最小深度为例如果你写成这样// 错误写法 int minDepth(TreeNode* root) { if (root nullptr) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }虽然这里不会直接出现空指针访问因为递归函数最开始判断了空但上面说过它的逻辑是错的。而真正会触发空指针报错的写法通常是在某些自定义的遍历函数中忘记对node-left做判空就直接访问node-left-val。排查这类问题的通用方法是每次使用指针前先确认它不为空在递归函数的开头始终处理“空节点”的情况。这是二叉树题目的铁律。4.2 无限递归导致的栈溢出无限递归的表现通常有两种程序直接崩溃报stack overflow或者力扣显示“Time Limit Exceeded”。很多初学者在写最小深度递归时没有正确处理左右子树为空的情况导致代码在某个特殊的树结构上不断自我调用永远无法到达递归出口。比如这种写法int minDepth(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 1; // 少了左空/右空判断但通常不会死循环 return 1 min(minDepth(root-left), minDepth(root-right)); }这段代码其实不会死循环但逻辑错误。真正容易死循环的场景是在处理“循环依赖”的数据结构时对二叉树来说无限递归多半是递归出口条件写错或者递归参数没有更新。遇到栈溢出时我的排查步骤是在递归函数最开始打印root的值看递归是否在某个节点反复进入。检查递归出口条件是否完整覆盖了所有空节点情况。如果树本身有环这通常意味着输入不合法需要额外引入set或map去记录访问过的节点。不过对于力扣的二叉树题目输入一定是合法的二叉树所以树中不会出现环无限递归基本都来自没有正确剪枝或出口写错。4.3 用测试用例验证你的解法写完后我建议至少用下面几类用例自测空树[]应返回 0。单节点[1]应返回 1。完全二叉树[3,9,20,null,null,15,7]应返回 2。这里叶子节点是 9 和 15、7 下面的空位最近叶子是 9深度是 2。只有左子树的链式树[1,2,null,3,null]应返回 3。因为没有右子树所有路径都必须往左走最终深度就是路径上节点总数。根节点只有右子树[1,null,2]应返回 2。这专门用来验证是否正确处理“右子树存在左子树为空”的分支。这些用例聊胜于无其实非常关键。我见过太多人提交一次不过看错误用例是[1,2]才发现自己没处理单边树的情况。4.4 小技巧在本地调试时如何快速构造二叉树力扣要求的输入格式是层序遍历的数组比如[3,9,20,null,null,15,7]。但在本地 IDE 调试时你不可能总靠手写new TreeNode去构造一棵大一点的树。这里分享一个我常用的方法写一个从层序数组构建二叉树的辅助函数。#include vector #include queue using namespace std; TreeNode* buildTree(vectorint nums) { if (nums.empty()) return nullptr; TreeNode* root new TreeNode(nums[0]); queueTreeNode* q; q.push(root); int idx 1; while (!q.empty() idx nums.size()) { TreeNode* node q.front(); q.pop(); if (idx nums.size() nums[idx] ! -1) { // 用 -1 表示空节点 node-left new TreeNode(nums[idx]); q.push(node-left); } idx; if (idx nums.size() nums[idx] ! -1) { node-right new TreeNode(nums[idx]); q.push(node-right); } idx; } return root; }注意我在这里用-1代替null因为vectorint没法直接表示空节点。如果你用vectorint存-1构造好树之后可以再用一个deleteTree函数释放内存避免内存泄漏虽然力扣不检查但本地跑多了内存会涨。这种辅助函数一次写好之后所有二叉树题目都能复用强烈建议存下来。5. 扩展思考从二叉树最小深度看一类递归题5.1 类似的二叉树路径长度问题最小深度其实是二叉树“路径问题”的一种。同类问题还有求二叉树的最大深度LeetCode 104。求二叉树中最长路径上的节点数树的直径LeetCode 543。判断二叉树是否平衡LeetCode 110核心是左右子树高度差不超过 1。求从根到叶子节点数字之和LeetCode 129。这些题都有一个共通点都需要在递归过程中计算“以某个节点为起点向下延伸的路径长度”并且都需要正确处理空节点和叶子节点的边界。掌握了最小深度题目的边界处理再去做这些题会顺手很多。5.2 如果二叉树变成 N 叉树有面试官会追问如果是 N 叉树求最小深度怎么写思路一致只是从判断两个子节点变成遍历所有子节点。C 的节点结构大概是class Node { public: int val; vectorNode* children; Node(int _val) : val(_val) {} };递归逻辑变成叶子节点的定义从“左右孩子都为空”改为“children列表为空”单侧分支的讨论也从两个分支变成多个分支但核心思想不变——只能从非空的子节点中找最小深度。5.3 引申二叉树的深度与 LeetCode 其他热门题目的关联在 LeetCode 热题 100 和周赛里很多题表面上和“最小深度”无关但底层都用到了类似的分层遍历或递归深度计算。比如“腐烂的橘子”LeetCode 994用的是 BFS 分层扩散和层序遍历求最小深度在“层”的统计方式上完全一致。“二叉树的层序遍历”LeetCode 102和 BFS 求最小深度的代码结构高度相似。“搜索二叉树”相关问题经常需要递归判断左右子树的范围这与最小深度递归中对左右子树分别判断的思路如出一辙。“满二叉树”的深度计算可以直接用对数公式因为所有节点都在不会出现空子树的情况这也是为什么很多刚入门的人觉得满二叉树比普通二叉树简单。另外如果你感兴趣可以去看一下“线索二叉树”的概念。线索二叉树利用空指针来记录前驱和后继节点减少递归时的空间开销。理解了“空指针不是没有用”这一层再回来看最小深度题里“遇到空边界要特殊处理”的逻辑会更有体感。5.4 从最小深度延伸到写代码的通用习惯这道题虽然只有十几行代码但它反映出的习惯很重要第一永远在递归函数开头处理空值。这个习惯能避免 90% 的空指针运行时错误。第二把复杂的边界条件显式写出来不要试图用一个精简的表达式“巧妙”地绕过它。面试评分时考官更看重你能不能把边界情况想清楚而不是代码有多短。第三写完代码后不要急着提交先在脑子里跑一遍特殊用例。我刷题这几年最稳定的提分方法就是“自测用例驱动开发”——先列测试用例再写代码逻辑。6. 写在最后这道题给我的一些刷题经验二叉树这类题看起来是数据结构题但本质上考的是递归思维和边界情况处理。最小深度之所以比最大深度更值得唠就是因为它逼着你跳出“无脑递归”的舒适区真正理解叶子节点、空节点、单边子树这些概念之间的微妙关系。我个人在实际刷题中的体会是遇到这种题目先在草稿纸上画出三四种不同形态的树再对着 1.2 节那五个边界条件逐一验证最后再落代码。这样做虽然前期会慢一点但能帮你省下后面反复提交失败的时间。最后再分享一个小技巧如果你的解法在某个用例上报错但报错的输入很长看不懂你可以手动把它简化成一个最小复现样例。比如把一棵大树裁剪成[1, null, 2, null, 3]这条链再看看问题出在哪。几乎所有二叉树相关的“运行时错误”都能用这种“最小复现 逐层分析”的方法定位。刷题不怕错怕的是不知道错在哪。希望这篇关于二叉树最小深度的拆解能帮你把这道简单题彻底吃透。
