Leetcode刷题记录33——二叉树的最小深度

题源：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

题目描述：

思路一：
使用 DFS 递归遍历的解法，每当遍历到一条树枝的叶子节点，就会更新最小深度，当遍历完整棵树后，就能算出整棵树的最小深度。
代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        # 记录最小深度（根节点到最近的叶子节点的距离）
        self.minDepthValue = float('inf')
        # 记录当前遍历到的节点深度
        self.currentDepth = 0

    def minDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        
        # 从根节点开始遍历
        self.traverse(root)
        return self.minDepthValue

    def traverse(self, root):    
        if root is None:
            return None
        
        # 在二叉树的前序位置进入节点时增加当前深度
        self.currentDepth += 1

        # 如果当前节点是叶子节点，更新最小深度
        if root.left is None and root.right is None:
            self.minDepthValue = min(self.minDepthValue, self.currentDepth)

        self.traverse(root.left)
        self.traverse(root.right)

        # 在二叉树的后序位置离开节点时减少当前深度
        self.currentDepth -= 1

执行时间如下，可以看出，DFS算法速度较慢，因为该算法必须确切的知道每条树枝的深度（根节点到叶子节点的距离），才能找到最小的那个：

思路二：
使用 BFS 层序遍历的解法。按照 BFS 从上到下逐层遍历二叉树的特点，当遍历到第一个叶子节点时，就能得到最小深度。
代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        q = deque([root])
        # root 本身就是一层, depth 初始化为1
        depth = 1

        while q:
            sz = len(q)
            # 遍历当前层的节点
            for _ in range(sz):
                cur = q.popleft()
                # 判断是否到达叶子节点
                if cur.left is None and cur.right is None:
                    return depth
                # 将下一层节点加入队列
                if cur.left is not None:
                    q.append(cur.left)
                if cur.right is not None:
                    q.append(cur.right)

            # 增加深度
            depth += 1
        return depth

执行时间如下，由于 BFS 逐层遍历的逻辑，第一次遇到目标节点时，所经过的路径就是最短路径，算法可能并不需要遍历完所有节点就能提前结束：