示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文基于 doocs/leetcode 仓库中 0111.Minimum Depth of Binary Tree 的题解文档深入剖析「二叉树的最小深度」这一经典二叉树问题。文章将从题意解读、关键难点出发完整讲解递归深度优先搜索与队列层序遍历广度优先搜索两种解法的推导思路、复杂度分析并给出 Python、Java、C、Go、TypeScript、Rust、JavaScript、C 共 8 种语言的实现读者阅读后可熟练掌握树上的最短路径问题的通用建模方法。题目描述给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明叶子节点是指没有子节点的节点。示例 1示例 1 的二叉树结构输入root [3,9,20,null,null,15,7] 输出2示例 2输入root [2,null,3,null,4,null,5,null,6] 输出5提示树中节点数的范围在[0, 10^5]内-1000 Node.val 1000解题前的关键思考这道题虽然代码量不大却藏着一个极其容易踩坑的点「只有一侧孩子」的节点不是叶子。叶子节点的定义是没有子节点的节点最小深度是从根到最近叶子的路径上的节点数。如果某个节点只有左子树或只有右子树那么它的另一侧是null。若把缺失的孩子当成深度0参与比较就会错误地返回当前深度1而实际上根到该节点并没有形成一条完整的、以叶子结尾的路径。例如示例 2 的root [2,null,3,null,4,null,5,null,6]每一个节点都只有右孩子树退化成一条链最小深度就是链的长度5。如果按空子树算 0的朴素写法1 min(minDepth(left), minDepth(right))会得到错误答案1。因此正确的思路是空树返回0缺左子树时返回1 右子树的最小深度缺右子树时返回1 左子树的最小深度两侧子树都在时返回1 min(左子树最小深度, 右子树最小深度)。由于节点规模可达10^5两种主流解法递归 DFS 与 BFS都能在O(n)时间内完成具体选择取决于树的形态。方法一递归深度优先搜索思路推导递归的终止条件是当前节点为空此时返回0如果当前节点左右子树有一个为空返回不为空的子树的最小深度加1如果当前节点左右子树都不为空返回左右子树最小深度的较小值加1。这一思路恰好对应上面的思考结论最小深度是根到最近叶子的节点数。注意「只有一侧孩子」的节点不是叶子必须继续走向仅有的那一侧否则会把缺失的孩子当成深度 0。递归时空树为 0缺左则 1 加上右子树最小深度缺右同理两侧都在则取较小者加 1。复杂度分析时间复杂度O(n)每个节点至多被访问一次n为二叉树节点个数空间复杂度O(n)递归调用栈的深度取决于树高最坏情况下链状树为O(n)。多语言实现Python3class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 if root.left is None: return 1 self.minDepth(root.right) if root.right is None: return 1 self.minDepth(root.left) return 1 min(self.minDepth(root.left), self.minDepth(root.right))对应仓库源码Solution.pyJavaclass Solution { public int minDepth(TreeNode root) { if (root null) { return 0; } if (root.left null) { return 1 minDepth(root.right); } if (root.right null) { return 1 minDepth(root.left); } return 1 Math.min(minDepth(root.left), minDepth(root.right)); } }对应仓库源码Solution.javaCclass Solution { public: int minDepth(TreeNode* root) { if (!root) { return 0; } if (!root-left) { return 1 minDepth(root-right); } if (!root-right) { return 1 minDepth(root-left); } return 1 min(minDepth(root-left), minDepth(root-right)); } };对应仓库源码Solution.cppGofunc minDepth(root *TreeNode) int { if root nil { return 0 } if root.Left nil { return 1 minDepth(root.Right) } if root.Right nil { return 1 minDepth(root.Left) } return 1 min(minDepth(root.Left), minDepth(root.Right)) }对应仓库源码Solution.goTypeScriptfunction minDepth(root: TreeNode | null): number { if (root null) { return 0; } const { left, right } root; if (left null) { return 1 minDepth(right); } if (right null) { return 1 minDepth(left); } return 1 Math.min(minDepth(left), minDepth(right)); }对应仓库源码Solution.tsRustuse std::cell::RefCell; use std::rc::Rc; impl Solution { fn dfs(root: OptionRcRefCellTreeNode) - i32 { if root.is_none() { return 0; } let node root.as_ref().unwrap().borrow(); if node.left.is_none() { return 1 Self::dfs(node.right); } if node.right.is_none() { return 1 Self::dfs(node.left); } 1 Self::dfs(node.left).min(Self::dfs(node.right)) } pub fn min_depth(root: OptionRcRefCellTreeNode) - i32 { Self::dfs(root) } }对应仓库源码Solution.rsJavaScriptvar minDepth function (root) { if (!root) { return 0; } if (!root.left) { return 1 minDepth(root.right); } if (!root.right) { return 1 minDepth(root.left); } return 1 Math.min(minDepth(root.left), minDepth(root.right)); };对应仓库源码Solution.jsC#define min(a, b) (((a) (b)) ? (a) : (b)) int minDepth(struct TreeNode* root) { if (!root) { return 0; } if (!root-left) { return 1 minDepth(root-right); } if (!root-right) { return 1 minDepth(root-left); } int left minDepth(root-left); int right minDepth(root-right); return 1 min(left, right); }对应仓库源码Solution.c方法二BFS广度优先搜索 / 层序遍历思路推导方法一可能先走完整棵深树才遇到最近叶子例如一棵深度极大但最近叶子很浅的树递归会先深入一侧。而最小深度对应的是最短路径BFS 按层扩张第一次到达叶子即可停止在偏斜树上往往常数更小、提前返回。实现要点使用队列实现广度优先搜索初始时将根节点加入队列。每次从队列中取出一个节点如果该节点是叶子节点则直接返回当前深度如果该节点不是叶子节点则将该节点的所有非空子节点加入队列。继续搜索下一层节点直到找到叶子节点。复杂度分析时间复杂度O(n)最坏情况下需要遍历到最后一层n为二叉树节点个数空间复杂度O(n)队列中最多同时存放某一层的全部节点最坏情况满二叉树的最后一层约为n/2的量级即O(n)。多语言实现Python3class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if root is None: return 0 q deque([root]) ans 0 while 1: ans 1 for _ in range(len(q)): node q.popleft() if node.left is None and node.right is None: return ans if node.left: q.append(node.left) if node.right: q.append(node.right)对应仓库源码Solution2.pyJavaclass Solution { public int minDepth(TreeNode root) { if (root null) { return 0; } DequeTreeNode q new ArrayDeque(); q.offer(root); int ans 0; while (true) { ans; for (int n q.size(); n 0; n--) { TreeNode node q.poll(); if (node.left null node.right null) { return ans; } if (node.left ! null) { q.offer(node.left); } if (node.right ! null) { q.offer(node.right); } } } } }对应仓库源码Solution2.javaCclass Solution { public: int minDepth(TreeNode* root) { if (!root) { return 0; } queueTreeNode* q{{root}}; int ans 0; while (1) { ans; for (int n q.size(); n; --n) { auto node q.front(); q.pop(); if (!node-left !node-right) { return ans; } if (node-left) { q.push(node-left); } if (node-right) { q.push(node-right); } } } } };对应仓库源码Solution2.cppGofunc minDepth(root *TreeNode) (ans int) { if root nil { return 0 } q : []*TreeNode{root} for { ans for n : len(q); n 0; n-- { node : q[0] q q[1:] if node.Left nil node.Right nil { return } if node.Left ! nil { q append(q, node.Left) } if node.Right ! nil { q append(q, node.Right) } } } }对应仓库源码Solution2.goTypeScriptfunction minDepth(root: TreeNode | null): number { if (!root) { return 0; } const q [root]; let ans 0; while (1) { ans; for (let n q.length; n; --n) { const node q.shift(); if (!node.left !node.right) { return ans; } if (node.left) { q.push(node.left); } if (node.right) { q.push(node.right); } } } }对应仓库源码Solution2.tsJavaScriptvar minDepth function (root) { if (!root) { return 0; } const q [root]; let ans 0; while (1) { ans; for (let n q.length; n; --n) { const node q.shift(); if (!node.left !node.right) { return ans; } if (node.left) { q.push(node.left); } if (node.right) { q.push(node.right); } } } };对应仓库源码Solution2.js两种解法对比与选型建议维度方法一递归DFS方法二BFS层序核心思想自底向上分治缺哪侧走哪侧两侧都在取较小者自顶向下按层扩张遇到第一个叶子立即返回时间复杂度O(n)O(n)空间复杂度O(n)递归栈取决于树高O(n)队列取决于某一层宽度平均情况需遍历完树才能确定答案找到最近叶子即停止通常访问的节点更少极端情况链状树会一直递归到最深处链状树每层只有一个节点队列始终很小效率稳定代码简洁度更简洁接近题意的直接翻译略繁琐需要显式维护队列与层计数选型建议追求代码简洁、便于记忆优先递归法三行核心逻辑即可覆盖所有情况树的形态偏斜、最近叶子较浅优先 BFS可以在到达最近叶子时立刻终止避免无谓的深层递归注意空树特判两种方法都必须在入口处对root null返回0节点数为 0最小深度为 0。在 doocs/leetcode 仓库中查看完整题解本题目解文档位于仓库的 solution/0100-0199/0111.Minimum Depth of Binary Tree 目录下结构与仓库内其他题目保持一致README.md中文题解包含题目描述、示例、提示以及上述两种解法的完整推导与多语言实现README_EN.md对应的英文题解Solution.*系列文件方法一递归的独立源码按语言分别命名为Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cSolution2.*系列文件方法二BFS的独立源码命名规则同上images/ex_depth.jpg示例 1 的二叉树示意图。仓库中所有 LeetCode 题解均按题号区间组织如solution/0000-0099、solution/0100-0199等每个题目目录都遵循 README 讲解 多语言独立源码 的规范布局便于读者按题号检索、对照学习。本文所展示的全部代码均可在对应路径下找到原始文件供本地运行验证。小结二叉树的最小深度是一道短小精悍的经典题理解叶子定义是解题的关键前提单侧为空的节点绝不能当作深度 0 的叶子递归法DFS将问题分解为缺哪侧走哪侧、两侧都在取较小的清晰子问题代码最简BFS 层序遍历把问题还原为最短路径的本质第一次触达叶子即可提前返回在偏斜树上表现更佳两种方法时间复杂度均为O(n)空间复杂度均为O(n)选型时可结合树的形态与代码可读性权衡。掌握本题后可以进一步将最短路径 提前终止的 BFS 思路迁移到其他树与图的最短路径问题中例如二叉树的层序遍历、图的最短无权路径等场景。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 111. 二叉树的最小深度递归 DFS 与 BFS 层序解法全剖析InterviewGuide 精选力扣 DFS 系列LeetCode 111. 二叉树的最小深度递归 DFS 与 BFS 层序解法全剖析InterviewGuide 精选力扣 DFS 系列 本文基于 Int教程doocs/leetcode 题解精读LeetCode 111 二叉树的最小深度——递归与 BFS 双解法的原理与实现doocs/leetcode 题解精读LeetCode 111 二叉树的最小深度——递归与 BFS 双解法的原理与实现 本文精读 doocs/leetcode示例工程N 叉树最大深度双解法实战DFS 递归与 BFS 层序在 LogicStack-LeetCode 中的完整实现N 叉树最大深度双解法实战DFS 递归与 BFS 层序在 LogicStack LeetCode 中的完整实现 本篇技术指南基于开源仓库 LogicStack教程文档上一篇探索古老与现代的交汇ELKS操作系统下一篇Aspire CLI 的 API 文档命令组aspire docs api 的设计规格与源码实现解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考