宽度优先搜索-(BFS)
宽度(广度)优先搜索(BFS)是一种经典的的搜索算法,这种算法一般会遍历整个数据来寻找最佳的数据。根据BFS的定义一般使用队列进行判断运算。
从上到下打印二叉树
本质也是二叉树的宽度遍历
代码如下:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
## 从上到下打印二叉树
## 这是一个典型宽度优先搜索(BFS)的例题
## BFS的典型策略是
## 1. 定义一个队列保存二叉树每一层的节点
## 2. 判断队列是否为空: 为空则跳出,否则进行下一层运算
#### 3. 遍历每一层的节点
#### 4. 节点出队,获得节点value,判断left and right
#### 5. 存在则加入队列
#### 6. 继续循环判断
if root is None:
return []
results, queue = [], collections.deque()
queue.append(root)
while queue:
temp = [] # 保存每一层的数据
for _ in range(len(queue)): # 控制队列大小正好是每一层数据大小
node = queue.popleft() # 出队
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
results.append(temp)
return results
网友评论