LeetCode 111. 二叉树的最小深度

Categories:

Tags:

题目描述
思路分析
1. 解法一：BFS 层序遍历（推荐）
2. 解法二：递归 DFS
相似题目

题目描述

✅ 111. 二叉树的最小深度

思路分析

解法一：BFS 层序遍历（推荐）

核心思路：

使用队列对二叉树进行层序遍历，逐层处理节点。

当第一次遇到叶子节点（左右子树均为空）时，当前层数即为最小深度。

BFS 天然保证第一个遇到的叶子节点一定是最近的叶子节点，无需遍历全树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点数，最坏情况下需要遍历所有节点。

空间复杂度：O(n)，其中 n 表示二叉树的节点数，队列中最多存储一层的节点数。

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 cur = queue.poll();

                // 遇到叶子节点，直接返回当前深度
                if (cur.left == null && cur.right == null) {
                    return depth;
                }

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.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++ {
			cur := queue[0]
			queue = queue[1:]

			// 遇到叶子节点，直接返回当前深度
			if cur.Left == nil && cur.Right == nil {
				return depth
			}

			if cur.Left != nil {
				queue = append(queue, cur.Left)
			}
			if cur.Right != nil {
				queue = append(queue, cur.Right)
			}
		}
		depth++
	}

	return depth
}

解法二：递归 DFS

核心思路：

递归计算左右子树的最小深度。

关键点：叶子节点是左右子树均为空的节点。若某一侧子树为空，不能直接取 min(left, right)，因为空子树深度为 0，不代表叶子节点方向。

处理策略：若左子树为空，只递归右子树；若右子树为空，只递归左子树；两侧均不为空，则取两侧最小值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树的节点数，每个节点只访问一次。

空间复杂度：O(h)，其中 h 表示二叉树的高度，递归栈深度最大为 h，最坏情况下退化为 O(n)。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 左子树为空，只递归右子树（右侧才有叶子节点）
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }

        // 右子树为空，只递归左子树（左侧才有叶子节点）
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }

        // 左右子树均不为空，取两侧最小深度
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        return Math.min(left, 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)

	return min(left, right) + 1
}

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	递归 / DFS / BFS
102. 二叉树的层序遍历	中等	BFS / 队列
110. 平衡二叉树	简单	递归 / 后序遍历
543. 二叉树的直径	简单	递归 / 后序遍历
112. 路径总和	简单	DFS / 递归
559. N 叉树的最大深度	简单	递归 / BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/76438130