二叉树的层序遍历

1、题目

图1

2、题解

广度优先搜索

借助数据结构队列，实现逐层打印

算法流程：

• 根节点为空时，返回空列表
• 初始化队列为根节点
• 当队列为空时跳出循环：
  • 新建临时结果列表用于存储当前层结果和临时队列用于存储下一层结果
  • 遍历队列，将结果存储临时结果列表，若当前节点的左(右)子节点不为空，则将临时节点加入临时队列
  • 令队列等于临时队列
• 返回结果列表

# 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: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        stack = [root]
        ans = []
        while stack:
            val = []
            tmp = []
            for node in stack:
                val.append(node.val)
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            ans.append(val)
            stack = tmp  

        return ans