【LeetCode111】二叉树的最小深度

题目描述

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

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

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

思路与算法

广度优先搜索（BFS）非常适合这个问题，因为它逐层探索树。这意味着我们遇到第一个叶子节点时，就可以返回。这比递归（虽然也能做）大大降低了时间复杂度。

1. BFS机制：
   • 我们使用队列来跟踪节点及其对应的深度。
   • 对于每个节点，我们检查它是否是叶子节点。如果是，我们立即返回它的深度。
   • 否则，我们将它的子节点添加到队列中，并将它们的深度增加 1。
2. edge case: 如果树是空的（即根是 None ），我们返回 0。

代码

# 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:
        # edge case
        if not root:
            return 0
        
        # initialize a queue for BFS
        # element: tuple(node, depth)
        queue = deque([(root, 1)])

        while queue:
            node, depth = queue.popleft()

            if not node.left and not node.right:
                return depth
            
            if node.left:
                queue.append((node.left, depth+1))
            if node.right:
                queue.append((node.right, depth+1))
            
        # Although we should always return from inside the loop once a leaf is found,
        # we include this return as a safeguard.
        return 0

总结

1. 该算法的运行时间为 O(n)，因为每个节点最多处理一次。
2. While a DFS approach (recursive) is also possible, BFS is generally preferred for finding the minimum depth because it stops as soon as a leaf is encountered, avoiding unnecessary exploration.