LeetCode 590: N-ary Tree Postorder Traversal

Meta Data

#

Difficulty: easy First Attempt: 2022-08-27

• Submissions: Runtime Error → Accepted ×5

Approach

#

Post-order handles each child in order and the node last (Tree). An iterative trick: the order “root, last child, …, first child” reversed is exactly post-order. So pop and record, push children in order, and reverse at the end.

My Attempts

#

Attempt 1 used an undefined variable; after that the recursive version passed directly.

Solution

#

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res, stack = [], [root] if root else []
        while stack:
            node = stack.pop()
            res.append(node.val)
            stack.extend(node.children)
        return res[::-1]

Complexity

#

Time O(n), space O(n).

Mistakes to Avoid

#

• The reversal trick requires pushing children in their original order.

Interview Explanation

#

Post-order reversed is root, then children from last to first, so I traverse in that order with a stack and reverse the result. Time O(n).