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

Constraints:

• The height of the n-ary tree is less than or equal to 1000

• The total number of nodes is between [0, 10^4]

💡 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

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> levelOrder(Node root) {
        /* base case */
        if(root == null) return ans;
        
        recursive(root, 0);
        return ans;
    }
    
    public void recursive(Node root, int level) {
        if(ans.size() == level) {
            ans.add(new ArrayList<>());
        }
        
        ans.get(level).add(root.val);
        
        for(Node node: root.children) {
            recursive(node, level + 1);
        }
    }
}