0429._N-ary_Tree_Level_Order_Traversal.md

429. N-ary Tree Level Order Traversal

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/n-ary-tree-level-order-traversal/

内容描述

Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

 



 

We should return its level order traversal:

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

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

level order的变体，简单

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res, cur_level = [], [root]
        while cur_level:
            next_level, tmp_res = [], []
            for node in cur_level:
                tmp_res.append(node.val)
                for child in node.children:
                    next_level.append(child)
            res.append(tmp_res)
            cur_level = next_level
        return res