LeetCode Binary Tree Postorder Traversal：遞歸與迭代解法

題目描述

給定一棵二元樹，回傳其節點值的後序遍歷序列。後序順序：左子樹 → 右子樹 → 根節點。
範例：輸入 {1,#,2,3} (1 為根，右子為 2，2 的左子為 3)，輸出 [3,2,1]。

遞歸解法 (簡單直觀)

時間複雜度 O(n)，空間複雜度 O(h) (h 為樹高，遞歸棧)。

public List postorderTraversal(TreeNode root) {
    List result = new LinkedList<>();
    postorder(root, result);
    return result;
}

private void postorder(TreeNode node, List res) {
    if (node == null) return;
    postorder(node.left, res);
    postorder(node.right, res);
    res.add(node.val);
}

迭代解法 (單棧 + 前驅指標)

模擬遞歸過程，需追蹤上一次訪問的節點以判斷是否已處理右子樹。

public List postorderTraversalIterative(TreeNode root) {
    List res = new ArrayList<>();
    if (root == null) return res;
    Deque stack = new ArrayDeque<>();
    TreeNode prev = null;
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.peek();
        if (curr.right == null || curr.right == prev) {
            res.add(curr.val);
            stack.pop();
            prev = curr;
            curr = null;
        } else {
            curr = curr.right;
        }
    }
    return res;
}

迭代解法 (雙棧 / 反轉前序)

利用「根→右→左」的修正前序遍歷，最後反轉即得後序。程式碼極簡。

public List postorderTraversalTwoStacks(TreeNode root) {
    List res = new ArrayList<>();
    if (root == null) return res;
    Deque s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode n = s1.pop();
        s2.push(n);
        if (n.left != null) s1.push(n.left);
        if (n.right != null) s1.push(n.right);
    }
    while (!s2.isEmpty()) res.add(s2.pop().val);
    return res;
}

複雜度比較

總結

面試中通常要求迭代解法。推薦掌握「雙棧反轉法」 (易寫、易懂) 與「單棧前驅法」 (空間最優、標準模擬遞歸)。