What is the minimum depth of a binary tree?

The minimum depth is the shortest path from the root node to the nearest leaf node, measured in terms of the number of nodes.

How can BFS be applied to solve the Minimum Depth of Binary Tree?

BFS is used to traverse the tree level by level. The first leaf node encountered will provide the minimum depth.

What are the time and space complexities for the solution?

Both BFS and DFS solutions have a time complexity of O(N), where N is the number of nodes. The space complexity is O(N) due to the need to store nodes during traversal.

How does DFS handle unbalanced trees in finding the minimum depth?

DFS can handle unbalanced trees by exploring one branch completely before backtracking. Early exit helps avoid unnecessary deep traversal when a leaf node is found.

What edge cases should be considered when solving this problem?

Edge cases include an empty tree, a tree with a single node, and trees with unbalanced depths where one branch is significantly deeper than the other.

#111

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例 1：输入： root = [3,9,20,null,null,15,7] 输出： 2 示例 2：输入： root = [2,null,3,null,4,nul…

树深度优先搜索广度优先搜索二叉树

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 10⁵] 内
-1000 <= Node.val <= 1000

lightbulb

解题思路

方法一：递归

递归的终止条件是当前节点为空，此时返回 $0$ ；如果当前节点左右子树有一个为空，返回不为空的子树的最小深度加 $1$ ；如果当前节点左右子树都不为空，返回左右子树最小深度的较小值加 $1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.minDepth(root.right)
        if root.right is None:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand the difference between BFS and DFS for this problem?
question_mark
Can you explain how early exit can improve the DFS approach?
question_mark
Will you consider edge cases such as an empty tree or trees with only one branch?

warning

常见陷阱

外企场景

error
Not considering edge cases like empty trees or a single-node tree.
error
Forgetting to handle unbalanced trees where one side is deeper than the other.
error
Misunderstanding the depth of the tree, confusing the total number of nodes with the path to a leaf node.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum depth of a binary tree using the same traversal methods.
arrow_right_alt
Solve for the depth of a binary tree where each node has only one child.
arrow_right_alt
Determine the depth of a binary search tree and compare it with its balanced version.

help

常见问题

外企场景

继续练习

#112 路径总和 #116 填充每个节点的下一个右侧节点指针 #117 填充每个节点的下一个右侧节点指针 II