遍历算法适用场景

在实际的使用场景中，DFS算法通常用来穷举所有路径，而BFS算法常用来寻找最短路径。因为二叉树的深度遍历和广度遍历就是DFS算法和BFS算法的简单应用。 下面以一道简单的例题说明其中的道理：LeetCode 111 二叉树的最小深度即根节点到最近叶结点的距离。而DFS深度遍历和BFS广度遍历都可以解决该题。

1. DFS遍历解法：

    # 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 __init__(self):
            self.min = float('inf')
            self.current = 0
               
        def traverse(self, root):
            if root is None:
                return
               
            self.current += 1
   
            if root.left is None and root.right is None:
                self.min = min(self.current, self.min)
               
            self.traverse(root.left)
            self.traverse(root.right)
               
            self.current -= 1
               
        def minDepth(self, root):
            if root is None:
                return 0
            self.traverse(root)
            return self.min
   

   • 需要注意的是，我们无法在不遍历完整棵树的情况下提前结束算法。必须确切地知道每条树枝的长度才能获得最小深度。
2. BFS遍历解法：

    # 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):
            if root is None:
                return 0
            # 将root放进列表中
            q = deque([root])
            depth = 1
               
            while q:
                size = len(q)
                for _ in range(size):
                    current = q.popleft()
                    if current.left is None and current.right is None:
                        return depth
                    if current.left is not None:
                        q.append(current.left)
                    if current.right is not None:
                        q.append(current.right)
                depth += 1
            return depth
   

   • 值得注意的是，与DFS算法不相同，BFS算法在不遍历完整个树的情况下可以提前结束算法，因为第一次碰到的叶结点一定是目标结点。