树类型模板
最常见的就是二叉树的层序遍历，我们能通过BFS算法模板直接套用进而秒杀。
例如：二叉树的层序遍历
题目：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例一：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
思路：
在本题中我们能把每层的节点都放在队列中，当访问每个节点的时候把节点的左右子树在添加到队列中（如果存在左右子树），同理还是访问子节点的子节点放到队列中，同时还需要输出每层的数据。
总所周知树也是图的一种，而我们一般使用多源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 levelOrder(self, root: TreeNode) -> List[List[int]]: #判断是否存在root if not root : return [] #用来统计输出的数据 res = [] #设置一个队列，并把头节点放入队列中 queue = [root] #开始对每一层的节点进行访问 while queue: #统计每一层节点的val值 temp = [] #获取每层的节点数 size = len(queue) #进行一个多源的BFS for _ in range(size): #出队列 r = queue.pop(0) #添加值 temp.append(r.val) #判断左右子节点是否存在，如果存在则入队 if r.left: queue.append(r.left) if r.right: queue.append(r.right) #把每层的数据放入res中 res.append(temp) return res
树的BFS习题已经给大家准备好了，给我直接秒杀他们！！！
图论类型模板
众所周知BFS其实就图的一种搜索方法，而在我们刷题的航向上经常遇见一些图的BFS搜索方法，所以今天就给大家带来图的BFS的秒杀解题模板。话不多说，直接上列题。
例题：310. 最小高度树
题目：
树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含n个节点的树，标记为0到n - 1。给定数字n和一个有n - 1条无向边的edges列表（每一个边都是一对标签），其中edges[i] = [ai, bi]表示树中节点ai和bi之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点x作为根节点时，设结果树的高度为h。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例：
输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
思路：
本题其实就是看谁的子节点多，就让谁来当作根节点。通过上图的示例我们也能看见1的根节点是比较多的一个节点，所以如果它作为根节点则就可以使树的长度达到最小。其实我们这个还能把这个树（或者图）看成是一个洋葱我们从外面一层层的拨开它的皮(节点（入度）为一的节点)。直到到最后一个能获取最后一个（或者多个节点）然后放到数组中并返回该数组中的所有节点。
我们可以通过下面画的一个简略图能大概的分析这个剥洋葱！（画的有点丑，大家别嫌弃嘿嘿嘿嘿）
通过上图能看到最中心的两个节点是最后一层拨开的节点，我们把它放在数组里面返回即可。
代码：
class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: #判断这个数是否小于两个节，小于就返回其有多少个就返回多少个。 if len(edges) < 2: return [i for i in range(n)] #统计1到n-1的每一个节点。 tree = [[] for i in range(n)] #用for循环把每个相连的节点放入里面，构建出我们想要的图。 for i, j in edges: tree[i].append(j) tree[j].append(i) #用一个数组对每个节点的入度进行统计 d = [len(i) for i in tree] #先把入度为一的节点放入队列中，也就是上图中最外面的那些节点。 queue = [i for i in range(len(d)) if d[i] == 1] res = None #使用队列进行循环 while queue: res = list() #进行多源BFS for j in range(len(queue)): #出队并且对每一层的节点放入到res数组中 src = queue.pop(0) res.append(src) #对每个节点的子节点进行循环判断 for i in tree[src]: #因为我们是先删除最外面的节点，但是随着外面的节点被删除，则和外面连接的节点的入度也会随着减一。 d[i] -= 1 #如果里面的节点的入度也是1的话，就接着放入队列中 if d[i] == 1: queue.append(i) return res
最近因为总结这个BFS模板题，博主基本上把力扣上面的大部分BFS题刷了一个遍。不过有一说一，用模板刷题是真的爽，每次ac就爽到爆炸。话不多bb，接着给大家安排一些习题也让大家爽一爽！！！！
