跳至主要內容

0429. N 叉树的层序遍历

ITCharge小于 1 分钟

0429. N 叉树的层序遍历open in new window

  • 标签:树、广度优先搜索
  • 难度:中等

题目大意

给定一个 N 叉树的根节点 root

要求:返回其节点值的层序遍历(即从左到右,逐层遍历)。

树的序列化输入是用层序遍历,每组子节点都由 null 值分隔。

解题思路

和二叉树的层序遍历类似。广度优先搜索每次取出第 i 层上所有元素。具体步骤如下:

  • 根节点入队。
  • 当队列不为空时,求出当前队列长度 sizesize
    • 依次从队列中取出这 sizesize 个元素,并将元素值存入当前层级列表 level 中。
    • 将该层所有节点的所有孩子节点入队,遍历完之后将这层节点数组加入答案数组中,然后继续迭代。
  • 当队列为空时,结束。

代码

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        ans = []
        if not root:
            return ans

        queue = [root]
        
        while queue:
            level = []
            size = len(queue)
            for _ in range(size):
                cur = queue.pop(0)
                level.append(cur.val)
                for child in cur.children:
                    queue.append(child)
            ans.append(level)

        return ans