Leetcode刷题：剑指offer【面试题32

【面试题32-2 分行从上到下打印二叉树】

难度： 简单

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

思路：由于要分层打印，每次入队后求一下队列的长度，仅将长度内（同一层）的节点放在一个列表里，就能实现分层打印啦。

代码逻辑：

• 初始化一个包含根节点的队列 queue，空的结果列表 res
• 获取当前队列长度（当前层节点个数），循环执行队首元素出队，将队首元素值添加到临时列表 layer 尾部，向 queue 中添加队首元素的左右子节点（若不为空）
• 将 layer 添加到结果列表 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 = [], [root]
        while queue:
            n = len(queue)
            layer = []
            for _ in range(n):  # print layer
                t = queue.pop(0)  # 时间复杂度：O(n)
                layer.append(t.val)
                if t.left: queue.append(t.left)
                if t.right: queue.append(t.right)
            res.append(layer)
        return res

同样可以用双端队列进行优化，使出队列的时间复杂度为 O(1)。

时间复杂度：O(n)，遍历节点个数为 n 的二叉树
空间复杂度：O(n)，最差情况下（平衡二叉树），同时有 n/2 个节点同时在 queue 中

# 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()  # 时间复杂度：O(1)
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res