LeetCode 111. 二叉树的最小深度
题目描述
题意分析
最小深度是从根节点到最近叶子节点的一条路径上，包含的节点数量。叶子必须左右孩子都为空，只有一个孩子的节点仍不是叶子。
空树的深度为
0，单节点树的深度为1。不存在的孩子不代表找到了一条长度为零的根到叶路径，因此不能把空侧的零直接与另一侧真实路径取最小值。题目最多有10^5个节点，下面分别给出直观的递归解法和适合深链的层序解法。
解法：DFS 区分单子树边界
核心思路
[!blue]
定义递归返回值为：从当前子树根出发，到这棵子树中最近叶子的路径节点数。当前根本身占一层，剩余长度由真正存在的孩子子树决定。
如果当前节点为空，返回
0。如果只有一个孩子，就只能沿着存在的那一侧继续走，答案是该侧最小深度加一；不能选择不存在的方向，因为它没有到达任何叶子。如果两个孩子都存在，根到叶的路径一定进入左子树或右子树，两侧各自的最短路径都有效，取较小者再加一即可。代码先处理左孩子为空，再处理右孩子为空；叶子也会进入第一个分支，由空右子树的
0加一得到1。每个节点都按其子树的正确答案计算自身，递归便逐层还原整棵树的最小深度。该写法使用与树高相同数量级的递归栈；树极深时，下面的 BFS 可以避免递归调用栈限制。
解题步骤
- 当前节点为空时返回
0。- 左孩子为空时，返回右子树最小深度加一；右孩子也为空时自然得到叶子的深度一。
- 右孩子为空时，返回左子树最小深度加一。
- 两个孩子都存在时，分别递归求深度，取最小值再加一。
代码实现
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null) {
// 左子树为空时沿右侧计算；若右侧也为空，本节点为叶子，返回 1。
return minDepth(root.right) + 1;
}
if (root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil {
// 空子树不能作为叶子路径参与最小值比较。
return minDepth(root.Right) + 1
}
if root.Right == nil {
return minDepth(root.Left) + 1
}
left := minDepth(root.Left)
right := minDepth(root.Right)
if left < right {
return left + 1
}
return right + 1
}
复杂度分析
设节点数为 $n$，树高为 $h$。
- 时间复杂度：$O(n)$，每个节点只访问一次；DFS 需要计算两侧子树的答案。
- 辅助空间复杂度：$O(h)$，用于递归栈，链状树时达到 $O(n)$。
关键点总结
[!green]
- 路径必须到真实叶子，不能把缺失的孩子当成终点。
- 只有一侧存在就沿该侧计算，两侧都存在才取最小值。
- 返回值统计节点数，所以每个非空当前节点都贡献一层。
解法二：BFS 寻找首个叶子
核心思路
[!blue]
层序遍历按深度从小到大访问节点，所以第一次遇到的叶子就是距离根最近的叶子，无需继续检查更深的节点。与 DFS 一直深入某条分支不同，BFS 会先检查完更浅的候选层。
队列先放入根节点，深度从
1开始。每层开始时保存队列当前长度，只处理这些节点，把它们的孩子放到队尾等待下一层。若本层遇到左右孩子都为空的节点，直接返回当前深度；否则整层处理完再把深度加一。队列代替了递归调用栈，长单链也能逐层处理。它的额外空间取决于树宽：链状树只需要很少的队列元素，较宽的树则可能保存较多同层节点。
解题步骤
- 空树返回
0，否则将根节点入队，设depth = 1。- 在每层开始时记录
levelSize，本轮只出队这么多个节点。- 若出队节点是叶子，返回
depth；否则把存在的左右孩子依次入队。- 本层结束后增加深度，继续处理下一层。
代码实现
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; 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 0;
}
}
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{
root,
}
depth := 1
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if node.Left == nil && node.Right == nil {
return depth
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
depth++
}
return 0
}
复杂度分析
设节点数为 $n$，最大层宽为 $w$。
- 时间复杂度：最坏为 $O(n)$，每个节点至多入队、出队一次；找到首个叶子后提前结束。
- 辅助空间复杂度：$O(w)$，队列同时保存当前层未处理节点及下一层已发现节点，最坏为 $O(n)$。
关键点总结
[!green]
- 按层访问保证首个叶子的深度最小，可以直接结束搜索。
- 固定每层初始队列长度，防止孩子被当成当前层节点。
- BFS 避免递归栈随树高增长，队列空间则随树宽增长。
易错点总结
[!yellow]
- 不区分孩子是否存在就写
1 + min(left, right)，会把空侧的零选为最短路径。- 叶子判定需要左右孩子同时为空，使用逻辑或会把单孩子节点误判成叶子。
- 空树返回
0，单节点树返回1，不能把节点数量误算成边数。- BFS 中必须在一层开始时固定节点数，当前层入队的孩子属于下一层，不能继续计入当前深度。
- BFS 遇到首个叶子即可返回；DFS 则不能因为先搜索到一个叶子就认为它一定最近。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 最大深度取较深分支，最小深度必须到真实叶子，不能把缺失孩子当成答案。 |
| 102. 二叉树的层序遍历 | 中等 | BFS逐层展开时，第一次遇到的叶子所在层就是最小深度。 |