Tree Medium

题目

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。例如，给定一个 3叉树 :

返回其层序遍历:
[
     [1],
     [3,2,4],
     [5,6]
]

树的深度不会超过 1000。树的节点总数不会超过 5000。

思路

方法一：利用双端队列实现广度优先搜索
我们要构造一个 sub-lists 列表，其中每个 sub-list 是树中一行的值。行应该按从左到右的顺序排列。因为我们从根节点开始遍历树，然后向下搜索最接近根节点的节点，这是广度优先搜索。我们使用队列来进行广度优先搜索，队列具有先进先出的特性。

在这里使用栈是错误的选择，栈应用于深度优先搜索。让我们在树上使用基于队列的遍历算法，看看它的作用。这是你应该记住的一个基本算法。

用一个列表存放节点值，队列存放节点。首先将根节点放到队列中，当队列不为空时，则在队列取出一个节点，并将其子节点添加到队列中。让我们看看这个算法遍历树时我们得到了什么结果。 我们可以看到它从左到右，并且从上到写顺序遍历节点。下一步，我们将研究如何如何在这个算法的基础上保存每一层的列表。

算法：
上面的基本算法在一定程度上帮助了我们解决这道题目，但是我们还需要保存每一层的列表，并且在根节点为空时正常工作。

再构造下一层的列表时，我们需要创建新的子列表，然后将该层的所有节点的值插入到列表中。一个很好的方法时在 while 循环体开始时记录队列的当前大小 size 。然后用另一个循环来处理 size 数量的节点。这样可以保证 while 循环在每一次迭代处理一层。

使用队列十分重要，如果使用 Vector ， List ， Array 的话，我们删除元素需要 O(N) 的时间复杂度。而队列删除元素只需要 O(1) 的时间。

复杂度分析

• 时间复杂度： O(N) ；N 指的是节点的数量。

• 空间复杂度： O(N) 。

  代码实现

  import collections
  class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root is None:
            return []
        result = []
        queue = collections.deque([root])
  
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                queue.extend(node.children)
            result.append(level)
        return result