宽度优先搜索-(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