def levelOrder(self, root: TreeNode) -> List[List[int]]:
outputList = []
# make sure to return a [] instead of None
if root is None:
return outputList
# set a queue to implement the BFS algorithm, and push root into it
nodeQueue = []
nodeQueue.append(root)
# keep searching until the last node has pop out and no more newNode
while nodeQueue:
# set a list to store the node of current Level
currentLevelList =[]
# the queue is keep changing, we need to keep the size of this level
# before adding or poping any node, otherwise the size would keep changing
levelSize = len(nodeQueue)
# loop through all the node of cuurent level
for i in range(levelSize):
# pop out the node, and store it into the list
currentNode = nodeQueue.pop(0)
currentLevelList.append(currentNode.val)
# check its children and push them into the queue,
# waiting for the next iteration of the next level
if currentNode.left is not None:
nodeQueue.append(currentNode.left)
if currentNode.right is not None:
nodeQueue.append(currentNode.right)
# after updating the currentLevel, add it to the output list
outputList.append(currentLevelList)
return outputList
BFS的使用场景
图的遍历 Traversal in Graph
最短路径 Shortest Path in Simple Graph
二叉树上的BFS
宽搜要点 BFS Key Points
Binary Tree Serialization
图上的BFS
(v1, v2, distance)，这个时候我们需要自己利用HashMap等数据结构来构建方便查找的图SoftCopy（拷贝reference）和DeepCopy（clone）（拷贝内容）的区别以及实际应用拓扑排序 Topological Sorting
棋盘上的BFS
矩阵 vs 图
图：
O(N^2)的级别O(N + M)O(M)问题也不大，因为M一般都比N大O(N^2)矩阵：
R*C个点，R*C*2条边（每个点上下左右4条边，每条边被2个点共享）。LC 200. Number of Islands
if语句，使代码简洁明了direction = [(0,1), (0,-1), (1,0), (-1,0)]AMZ Zombie in Matrix
LC 1197. Minimum Knight Moves