429. N叉树的层序遍历

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

返回其层序遍历:

[
[1],
[3,2,4],
[5,6]
]

说明:

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

解法一：带同层节点数量控制的BFS

普通的BFS并不检视队列长度，因此不知道当前队首元素是哪一层的。

在常规队列实现BFS的基础上引入层的控制。需要在当前层将所有节点的children取出，加入队列。下一层在处理时，队列的长度就是本层节点的数量。即对同层节点的处理应在一个for循环内完成，循环次数为当前队列中的元素数量，将属于本层的节点取空。

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        queue = [root] if root else []
        ans = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)
                queue.extend(node.children)
            ans.append(level)
        return ans

同类题型

102. 二叉树的层序遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        if root:
            queue.append(root)
        ans = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)
        return ans

103. 二叉树的锯齿形层次遍历

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = [root] if root else []
        l2r, ans = True, []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level if l2r else level[::-1])
            l2r = not l2r
        return ans