LeetCode #429 N-ary Tree Level Order Traversal

Posted on | Post modified | In , , , , , ,

Problem

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

Example

img

We should return its level order traversal:

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

Solution

Method: Breadth-first Search

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        ret = []
        queue = collections.deque([(root, 1)])
        
        while queue:
            node, level = queue.popleft()
            if node:
                if level > len(ret):
                    ret.append([])
                
                ret[-1].append(node.val)
                
                for child in node.children:
                    queue.append((child, level + 1))
        
        return ret