LeetCode 111: Minimum Depth of Binary Tree (First Leaf BFS)
LeetCode 111Binary TreeBFSDFSToday we solve LeetCode 111 - Minimum Depth of Binary Tree.
Source: https://leetcode.com/problems/minimum-depth-of-binary-tree/
English
Problem Summary
Given the root of a binary tree, return its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Key Insight
A leaf is a node with both children null. Using BFS level-order traversal, the first leaf we encounter is guaranteed to have the minimum depth.
Brute Force and Limitations
DFS can compute depth recursively, but if implemented carelessly it may treat missing children as depth 0 and return wrong answers. BFS avoids this pitfall and can stop early once the first leaf is found.
Optimal Algorithm Steps
1) If root is null, return 0.
2) Push root into a queue and set depth = 1.
3) Process nodes level by level.
4) When a node is a leaf, return current depth immediately.
5) Otherwise push non-null children and continue.
Complexity Analysis
Time: O(n) in the worst case.
Space: O(n) for the queue in the worst case.
Common Pitfalls
- Treating null child depth as 0 in DFS formula min(left, right) + 1 without special handling.
- Mistaking a node with only one child as a leaf.
- Forgetting BFS early return when first leaf is reached.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; 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 depth;
}
}func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
depth := 1
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; 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 depth
}class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth = 1;
while (!q.empty()) {
int size = (int)q.size();
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
if (node->left == nullptr && node->right == nullptr) {
return depth;
}
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
depth++;
}
return depth;
}
};from collections import deque
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
depth = 1
while q:
for _ in range(len(q)):
node = q.popleft()
if not node.left and not node.right:
return depth
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
depth += 1
return depthvar minDepth = function(root) {
if (root === null) {
return 0;
}
const queue = [root];
let depth = 1;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node.left === null && node.right === null) {
return depth;
}
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
depth++;
}
return depth;
};中文
题目概述
给定二叉树根节点，返回最小深度。最小深度指从根节点到最近叶子节点的最短路径上的节点数量。
核心思路
叶子节点必须是左右孩子都为空。使用层序 BFS 时，第一次遇到叶子节点所在层就是最小深度，可以立刻返回。
暴力解法与不足
DFS 递归也能做，但若直接写成 min(leftDepth, rightDepth) + 1，在单边子树场景会出错。BFS 天然支持“先到先得”的最短层返回。
最优算法步骤
1）若根节点为空，返回 0。
2）根节点入队，深度 depth 初始化为 1。
3）按层遍历队列。
4）当前节点若是叶子节点，立即返回 depth。
5）否则把非空子节点入队，继续下一层。
复杂度分析
时间复杂度：最坏 O(n)。
空间复杂度：最坏 O(n)（队列）。
常见陷阱
- 在 DFS 中把空子树深度当作 0，直接取 min 导致答案偏小。
- 把“只有一个孩子”的节点误判为叶子节点。
- BFS 找到第一个叶子后没有及时返回。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; 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 depth;
}
}func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
depth := 1
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; 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 depth
}class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth = 1;
while (!q.empty()) {
int size = (int)q.size();
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
if (node->left == nullptr && node->right == nullptr) {
return depth;
}
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
depth++;
}
return depth;
}
};from collections import deque
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
depth = 1
while q:
for _ in range(len(q)):
node = q.popleft()
if not node.left and not node.right:
return depth
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
depth += 1
return depthvar minDepth = function(root) {
if (root === null) {
return 0;
}
const queue = [root];
let depth = 1;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (node.left === null && node.right === null) {
return depth;
}
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
depth++;
}
return depth;
};
Comments