Minimum Depth of Binary Tree
LeetCode 111 二叉树最小深度：BFS 见到第一个叶子即返回；DFS 注意空子树处理。
#resource / algorithm
#type / howto
#status / evergreen
#ds / tree
#algo / bfs
#algo / dfs
#source / leetcode
[!info] related notes 算法面试题型 MOC 二叉树高频题
Minimum Depth of Binary Tree
LeetCode: https://leetcode.cn/problems/minimum-depth-of-binary-tree/
推荐：BFS
最小深度用 BFS 很自然：第一次遇到叶子节点时的层数就是答案。
import java.util.*;
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int depth = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
if (cur.left == null && cur.right == null) return depth;
if (cur.left != null) q.add(cur.left);
if (cur.right != null) q.add(cur.right);
}
depth++;
}
return depth;
}
}DFS 注意点
- 如果一个子树为空，最小深度不能取
min(left,right)直接得到 0，需要特殊处理。