0429. Level Order Traversal

Medium | Tree + Recursion / Stack | 32 ms (98.53%), 16.3 MB (96.69%)

❓ Problem Statement

Source: LeetCode - N-ary Tree Level Order Traversal GitHub: Solution / Performance

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

✍🏻 Constraints & Example

💡 Ideas

For the recursive solution, we need to record the extra information 'Level' in each iteration.

Then, based on the different levels in each recursion, we append the node's value to different lists.

🤖 Python3

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        # (base case)
        if not root: return []
        if not root.children: return [[root.val]]
        
        # ==================================================
        #  N-ary Tree + Level Order Traversal (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [root]
        
        while stack:
            tmp = []
            for i in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                
                for element in node.children: stack.append(element)
                    
            ans.append(tmp)
                    
        return ans

        '''
        # ==================================================
        #  N-ary Tree + Level Order Traversal (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        
        def recursive(node: 'Node', level: int) -> None:
            if len(ans) == level: ans.append([])
                
            ans[level].append(node.val)
            
            if node.children:
                for element in node.children:
                    recursive(element, level + 1)
        
        recursive(root, 0)
        return ans
        '''

🤖 Java