• 示例工程

本文基于 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)。

多语言实现

Python3

class 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.py

Java

class 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.java

C++

class 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.cpp

Go

func 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.go

TypeScript

function 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.ts

Rust

use std::cell::RefCell; use std::rc::Rc; impl Solution { fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> 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: Option<Rc<RefCell<TreeNode>>>) -> i32 { Self::dfs(&root) } }

对应仓库源码：Solution.rs

JavaScript

var 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.js

C

#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)。

多语言实现

Python3

class 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.py

Java

class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> 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.java

C++

class Solution { public: int minDepth(TreeNode* root) { if (!root) { return 0; } queue<TreeNode*> 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.cpp

Go

func 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.go

TypeScript

function 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.ts

JavaScript

var 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

两种解法对比与选型建议

选型建议：

• 追求代码简洁、便于记忆：优先递归法，三行核心逻辑即可覆盖所有情况；
• 树的形态偏斜、最近叶子较浅：优先 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.c；
• Solution2.*系列文件：方法二（BFS）的独立源码，命名规则同上；
• images/ex_depth.jpg：示例 1 的二叉树示意图。

仓库中所有 LeetCode 题解均按题号区间组织（如solution/0000-0099、solution/0100-0199等），每个题目目录都遵循 "README 讲解 + 多语言独立源码" 的规范布局，便于读者按题号检索、对照学习。本文所展示的全部代码均可在对应路径下找到原始文件，供本地运行验证。

小结

二叉树的最小深度是一道"短小精悍"的经典题：

• 理解叶子定义是解题的关键前提，单侧为空的节点绝不能当作"深度 0 的叶子"；
• 递归法（DFS）将问题分解为"缺哪侧走哪侧、两侧都在取较小"的清晰子问题，代码最简；
• BFS 层序遍历把问题还原为"最短路径"的本质，第一次触达叶子即可提前返回，在偏斜树上表现更佳；
• 两种方法时间复杂度均为O(n)，空间复杂度均为O(n)，选型时可结合树的形态与代码可读性权衡。

掌握本题后，可以进一步将"最短路径 + 提前终止"的 BFS 思路迁移到其他树与图的最短路径问题中，例如二叉树的层序遍历、图的最短无权路径等场景。

• 示例工程