二叉树的最小深度

难度: Easy

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

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

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

示例 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

Submission

运行时间: 480 ms

内存: 51.7 MB

# 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
from collections import deque


class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque()
        q.append(root)
        floor = 1
        while q:
            size = len(q)
            for _ in range(size):
                node = q.popleft()
                if node.left is None and node.right is None:
                    return floor
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            floor += 1

Explain

该题解使用广度优先搜索（BFS）的方法来解决二叉树的最小深度问题。具体思路如下： 1. 如果根节点为空，直接返回深度0。 2. 创建一个队列，并将根节点加入队列。 3. 初始化深度为1。 4. 当队列不为空时，进行以下操作： a. 获取当前队列的大小，表示当前层的节点数。 b. 遍历当前层的所有节点： - 从队列中取出节点。 - 如果该节点是叶子节点（左右子节点都为空），则返回当前深度。 - 如果该节点有左子节点，将左子节点加入队列。 - 如果该节点有右子节点，将右子节点加入队列。 c. 深度加1，继续下一层的遍历。

时间复杂度: O(n)

空间复杂度: O(w)

from collections import deque

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 如果根节点为空，直接返回深度0
        if root is None:
            return 0
        
        # 创建一个队列，并将根节点加入队列
        q = deque()
        q.append(root)
        
        # 初始化深度为1
        floor = 1
        
        # 当队列不为空时，进行遍历
        while q:
            # 获取当前队列的大小，表示当前层的节点数
            size = len(q)
            
            # 遍历当前层的所有节点
            for _ in range(size):
                # 从队列中取出节点
                node = q.popleft()
                
                # 如果该节点是叶子节点，则返回当前深度
                if node.left is None and node.right is None:
                    return floor
                
                # 如果该节点有左子节点，将左子节点加入队列
                if node.left:
                    q.append(node.left)
                
                # 如果该节点有右子节点，将右子节点加入队列
                if node.right:
                    q.append(node.right)
            
            # 深度加1，继续下一层的遍历
            floor += 1

Explore

在BFS中，我通过层序遍历来确保总是首先到达最近的叶子节点。因为BFS是按层（从根节点到叶子节点）进行的，所以确保了一旦遇到任何叶子节点，它必定是最近的叶子节点，因此可以立即返回其深度。

选择BFS的原因是它更适合于寻找最小深度。在使用DFS时，我们可能会首先深入到树的一个深层分支，而这个分支可能不包含最近的叶子节点。而BFS从根节点开始逐层向下搜索，一旦找到叶子节点，就可以确保这是到达叶子节点的最短路径。

在最坏情况下，队列中可能会包含与二叉树的最宽层一样多的节点。这种情况通常发生在每个节点都有两个子节点的完全二叉树中。例如，在完全二叉树的最后一层，如果树高为h，最后一层可能包含2^(h-1)个节点。

在节点出队后立即检查它是否是叶子节点可以避免不必要的操作，因为一旦确定一个节点是叶子节点，我们就可以返回其深度，不需要进一步探索其子节点。在将子节点加入队列前进行检查是不合适的，因为我们需要首先确认当前节点是否为叶子节点；如果不是，我们才需要考虑其子节点。