0589. Preorder Traversal

Easy | Tree + Recursion / Stack | 32 ms (98.74%), 16.4 MB (75.58%)

❓ Problem Statement

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

Given the root of an n-ary tree, return the preorder 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)

Follow up: Recursive solution is trivial, could you do it iteratively?

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].

• 0 <= Node.val <= 10^4

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

💡 Ideas

For recursive solution, visiting the children (list of nodes) in the right order.

For iterative solution, visiting the children (list of nodes) reversely.

Excepting the above hints, we append each node's value first before visiting the child nodes.

🤖 Python3

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

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    LinkedList<Integer> answer;
    
    public List<Integer> preorder(Node root) {
        answer = new LinkedList<Integer>();
        
        /* base case */
        if(root == null) return answer;
        
        answer.add(root.val);
        
        if(root.children == null) return answer;
        
        for(Node node: root.children) {
            recursive(node);
        }
        
        return answer;
    }
    
    public void recursive(Node root) {
        answer.add(root.val);
        
        if(root.children != null ) {
            for(Node node: root.children) {
                recursive(node);
            }
        }
    }
}