二叉树的层序遍历（广度搜索法） Python

本文介绍: 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

思路：

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

代码：

# 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

# 导入 collections 模块
import collections

class Solution:
    # 定义函数 levelOrder，参数为二叉树的根节点 root
    # 返回值为二维数组，表示二叉树的层序遍历结果
    def levelOrder(self, root: Optional[TreeNode]) -&gt; List[List[int]]:
        # 如果二叉树为空，直接返回空列表
        if not root:
            return []
        # 定义队列 queue，将根节点放入队列中
        queue = collections.deque([root])
        # 定义列表 res，用于存储每一层的节点值
        res = []
        # 当队列不为空时，循环遍历队列中的节点
        while queue:
            # 获取当前队列的长度
            size = len(queue)
            # 定义列表 level，用于存储当前层的节点值
            level = []
            # 循环遍历当前层的节点
            for i in range(size):
                # 弹出队列中的节点
                node = queue.popleft()
                # 将节点的值加入 level 列表中
                level.append(node.val)
                # 如果节点的左子树不为空，将左子树加入队列中
                if node.left:
                    queue.append(node.left)
                # 如果节点的右子树不为空，将右子树加入队列中
                if node.right:
                    queue.append(node.right)
            # 将当前层的节点值加入 res 列表中
            res.append(level)
        # 返回 res 列表，即为二叉树的层序遍历结果
        return res