💬 Discord
Sign In
NeetCode #384LC-145EasyTreesNC 250
← Back to All Problems

#384 · #145 · Binary Tree Postorder Traversal(二叉树的后序遍历)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its post-order traversal (left, right, root) as a list of values. Constraints: the number of nodes is in [0, 100]. The follow-up asks for an iterative solution.

💡 Core Algorithmic Approaches

  1. A neat trick: a modified pre-order that visits root, right, left produces the reverse of the post-order sequence.
  2. So push right before left (the opposite of pre-order), collect the values, then reverse the result.
  3. This avoids the fiddly state machine needed for a direct iterative post-order traversal.
  4. An alternative marks visited nodes with a second stack or a (node, visited) pair.

💻 Benchmark Python3 Implementation

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        st = [root]
        while st:
            node = st.pop()
            res.append(node.val)
            # push left first so right is processed first -> root, right, left
            if node.left:
                st.append(node.left)
            if node.right:
                st.append(node.right)
        return res[::-1]                   # reverse -> left, right, root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is pushed and popped once, plus one reversal.
💾 Space Complexity
O(n) for the stack and the result.

⚠️ Interview Pitfalls & Follow-ups

  • Pushing in pre-order order and forgetting the reversal: the output would be root, right, left.
  • Trying to do a direct iterative post-order with one stack: it requires tracking whether the right subtree has been visited, which is easy to get wrong.
  • Reversing the tree instead of the output: the traversal order is what matters.
  • Recursing on a deep tree: the recursion limit can be exceeded.