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

💡 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