0590. Postorder Traversal

Easy | Tree + Recursion / Stack | 32 ms (98.77%), 16.3 MB (94.57%)

❓ Problem Statement

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

Given the root of an n-ary tree, return the postorder 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 visit the child nodes first before appending each node's value.

🤖 Python3

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

        '''
        # ==================================================
        #  N-ary Tree + Post-order Traversal  (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        
        def recursive(node: 'Node') -> None:
            if node.children:
                for element in node.children:
                    recursive(element)
            
            ans.append(node.val)
        
        recursive(root)
        return ans
        '''

🤖 Java

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