剑指 Offer 32 - II. 从上到下打印二叉树 II（广度优先搜索）

题目描述

• 方法一：使用队列保存每层列表
• 方法二：用当前队列长度控制循环次数

# 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]]:
        if not root:
            return []
        res, queue = [], collections.deque()
        queue.append([root])    # 以列表形式存入，每个列表代表同层所有节点
        while queue:
            level_node_list = queue.popleft()
            next_level_node_list = []   # 保存下一层节点列表
            level_node_val_list = []    # 保存当前层节点值列表
            # 遍历该层节点
            for node in level_node_list:
                level_node_val_list.append(node.val)
                if node.left:
                    next_level_node_list.append(node.left)
                if node.right:
                    next_level_node_list.append(node.right)
            res.append(level_node_val_list)
            # 这一步是为了防止一直向queue中append一个空列表，造成queue永不为空
            if next_level_node_list:
                queue.append(next_level_node_list)
        return res

参考解法

# 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]]:
        if not root:
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            tmp = []    # 保存每层节点的临时列表
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res