💬 Discord
Sign In
NeetCode #385LC-590EasyTrees
← Back to All Problems

#385 · #590 · N-ary Tree Postorder Traversal(N 叉树的后序遍历)

📌 Problem Statement & Constraints

Given the root of an N-ary tree, return its post-order traversal (children left to right, then the node) as a list of values. Constraints: the number of nodes is in [0, 10^4], the depth is at most 1000.

💡 Core Algorithmic Approaches

  1. Recursion is the direct expression: recurse into each child, then append the node's value.
  2. Iteratively, a neat trick reuses the pre-order stack: visit root, child_n, ..., child_1 and reverse the result.
  3. Pushing children in their natural order and popping gives the reverse of the desired child order, which the final reversal fixes.
  4. Both approaches are O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def postorder(self, root: "Optional[Node]") -> List[int]:
        if not root:
            return []
        res = []
        st = [root]
        while st:
            node = st.pop()
            res.append(node.val)
            for c in node.children:        # natural order -> reversed on pop
                st.append(c)
        return res[::-1]                   # reverse -> children left to right, then node


# Recursive variant
class Solution2:
    def postorder(self, root: "Optional[Node]") -> List[int]:
        res = []

        def dfs(node: "Optional[Node]") -> None:
            if not node:
                return
            for c in node.children:
                dfs(c)
            res.append(node.val)           # node comes after its children

        dfs(root)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(n) for the stack or O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the final reversal: the traversal would come out as root, last child, ..., first child.
  • Appending the node before its children in the recursion: that produces a pre-order traversal.
  • Pushing children in reverse order: that would undo the effect of the final reversal.
  • Recursing on a depth-1000 tree: close to Python's recursion limit; the iterative form is safer.