二叉树的最小深度
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
树中节点数的范围在 [0, 105] 内，节点值在 [-1000, 1000] 范围内。
示例 1
示例 2
示例 3
模拟答题者思考
1. 暴力直觉：枚举所有根到叶子的路径，取最短节点数——正确，但共享前缀会被重复走，可优化。
2. 与 #104 最大深度的差别：最大深度可以对空子树当 0 取 max；最小深度必须到叶子，若只有一侧有子树，不能走「空侧深度 0」那条假路径。
3. BFS 按层扩展：离根近的层先处理，第一个遇到的叶子的深度就是答案（示例 1 先在深度 2 遇到 9，不必再等 15/7）。
4. DFS 后序：叶子返回 1；仅左或仅右时返回 1 + minDepth(非空子树)；双非空才 1 + min(左, 右)。错写 1 + min(left, right) 且空子树返回 0 时，[1,null,2] 会错成 1。
5. 每个节点入队/访问常数次，时间 O(n)；BFS 队列最坏 O(n)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
q | 队列 | 定义：待扩展的节点，元素为 (node, depth)，depth 为从根到该节点的节点数维护：按层从近到远扩展，保证第一次弹出的叶子即全局最近叶子 更新：根入队 (root, 1)；非叶子将孩子以 depth + 1 入队 |
node, depth | TreeNode*, int | 定义：当前处理的节点及其到根的路径长度 维护：仅当 node 为叶子（左右皆空）时，depth 才是合法答案候选更新：每轮 pop 队首；遇叶子立即 return depth |
minDepth(root)（DFS） | int | 定义：子树 root 到最近叶子的最小深度；空树 0维护：单子树时必须沿有孩子的那一侧走下去，不能把缺失侧当深度 0 参与 min更新：双孩子 1 + min(左, 右)；仅左/仅右则 1 + minDepth(非空侧) |
落码步骤
1. 若 root 为空，返回 0
2. 队列 q = [(root, 1)]
3. 循环：弹出 (node, depth)；若 node 为叶子，return depth
4. 若有左/右孩子，分别以 depth + 1 入队
5. （DFS 备选）单子树分支单独递归，双非空再取 min
代码实现
from collections import deque
class Solution:
def minDepth(self, root: TreeNode | None) -> int:
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) return 0;
std::queue<std::pair<TreeNode*, int>> q;
q.push({root, 1});
while (!q.empty()) {
auto [node, depth] = q.front();
q.pop();
if (!node->left && !node->right)
return depth;
if (node->left)
q.push({node->left, depth + 1});
if (node->right)
q.push({node->right, depth + 1});
}
return 0;
}
};
// 时间 O(n)，空间 O(w)复杂度分析
O(n)
O(w)（BFS 队列宽度，最坏 O(n)；DFS 递归栈 O(h)）
常见坑
照搬 #104：1 + min(maxDepth(left), maxDepth(right)) 且空子树返回 0——对 [1,null,2] 会得到 1，正确答案是 2。
把「仅有单孩子的节点」当叶子：必须左右都空才算叶子，否则还要继续向下。
DFS 在双非空与单子树分支混用同一公式：缺一侧时只能递归非空侧，不能对空侧取深度 0 再 min。
必测边界 Case
root = [] → 0
root = [1] → 1
root = [3,9,20,null,null,15,7] → 2
root = [2,null,3,null,4,null,5,null,6] → 5
root = [1,null,2] → 2（勿写成 1）