广度优先搜索（BFS)应用——层序遍历和最段路径

 BFS模板：

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS总共有两个模板：

模板1：如果不需要确定当前遍历到了哪一层，BFS模板如下。

 1 while queue 不空：
 2     cur = queue.pop()  // 弹出队列的头部元素当做当前遍历点
 3     for 节点 in cur的所有相邻节点：
 4         if 该节点有效且未访问过：
 5             queue.push(该节点)

模板2：如果要确定当前遍历到了哪一层，BFS模板如下。
这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
{
    size = queue.size()
    while (size --) 
    {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;
}

上面两个是通用模板，在任何题目中都可以用，是要记住的！

 应用一：层序遍历

LeetCode 102. Binary Tree Level Order Traversal 二叉树的层序遍历（Medium）

本题要求二叉树的层次遍历，所以同一层的节点应该放在一起，故使用模板二。

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        res = []
        q = [root]
        while q:
            temp = []
            for i in range(len(q)):  # 每一次循环输出一层
                r = q.pop(0)
                temp.append(r.val)
                if r.left:
                    q.append(r.left)
                if r.right:
                    q.append(r.right)
            res.append(temp)  # 记录temp(一层的数据）
        return res

 应用二：最短路径

参考文章：https://www.cnblogs.com/sbb-first-blog/p/13259728.html