145. Binary Tree Postorder Traversal

──────────────────────────────────────────────────────────────────────

後序遍歷：先走左子樹，再走右子樹，最後處理自己。

思路

遞迴版和前序 / 中序只差「處理自己」那一行的位置，所以 LeetCode 的 follow-up 一樣是：

Recursive solution is trivial, could you do it iteratively?

後序的 iterative 版是三種裡最難的，因為它的要求最違反棧的天性：必須等左右子樹都走完才能處理自己，也就是節點被「發現」和被「處理」之間隔得最遠。

但有一個很漂亮的繞路：

後序是「左 → 右 → 根」。把它反過來就是「根 → 右 → 左」—— 那是把前序的左右對調而已。

所以做法變成：用前序的寫法（一個棧、走到就處理），但進棧順序改成左先進、右後進，得到「根右左」，最後把結果反轉。前序能寫，後序就能寫。

後序為什麼是樹的主力

前序是「由上往下傳資訊」，後序是由下往上收集資訊 —— 而樹的中難題絕大多數都是後者：遞迴函式回傳子樹的某個統計量，父節點拿它算自己的。

最大深度 → 回傳子樹深度，取 max + 1（104）
直徑 → 回傳單邊最長，答案取左右相加（543）
最大路徑和 → 同上，但要處理負數（124）
樹形 DP → 回傳「選 / 不選」兩種狀態（337）

這一型的關鍵是回傳給父節點的值，和答案要的值常常不一樣（124 回傳單邊、答案取兩邊相加）。整理見 Tree 遍歷模板。

解題方向

遞迴

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        res.extend(self.postorderTraversal(root.left))
        res.extend(self.postorderTraversal(root.right))
        res.append(root.val)
        return res

「答案 = 左子樹 + 右子樹 + 自己」，好讀，但每層都在複製子樹的 list，複雜度會退化 —— 見下面的複雜度分析。

共用一個 res 的版本是嚴格 $O (n)$ ，也是實戰形狀（後序題幾乎都要在「處理自己」那一步做事，而不是拼 list）：

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)      # 後序：處理自己放最後面
        
        dfs(root)
        return res

Iterative：做「根右左」再反轉

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [root] if root else []

        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)    # 左先進、右後進 → 彈出時右先出
            if node.right:
                stack.append(node.right)

        return res[::-1]                   # 「根右左」反轉 = 「左右根」

和 144. 前序的 iterative 版比一比，只有兩處不同：進棧的左右順序對調、最後多一個 [::-1]。前序記住了，後序就是免費的。

面試講法：「後序不好直接用棧做，因為要等兩邊子樹都完成。但後序反轉就是根右左，那只是前序的鏡像，所以我先做根右左再反轉。」

如果面試官特別要求「不能反轉、要真正的後序順序」，就需要記住「這個節點的子樹是否已經處理過」——用一個 prev 指標或在棧裡存 (node, visited)。那個版本比較繁瑣，通常不是考點。

補充

四種遍歷一起看：144. 前序、94. 中序、145. 後序、102. 層序。

後序型的實戰題：104. Maximum Depth、543. Diameter of Binary Tree、124. Binary Tree Maximum Path Sum、337. House Robber III。

複雜度

遞迴（extend 版）

時間 $O (n \log n)$ ~ $O (n^{2})$ — 每一層都複製子樹的 list；平衡樹是 $O (n \log n)$ ，斜樹退化成 $O (n^{2})$
空間 $O (n)$ — 遞迴堆疊加上中途產生的暫時 list

遞迴（共用 res 版）

時間 $O (n)$ — 每個節點只 append 一次
空間 $O (h)$ — 只有遞迴堆疊

Iterative（根右左 + 反轉）

時間 $O (n)$ — 每個節點進棧出棧各一次，反轉再花 $O (n)$
空間 $O (h)$ — 棧裡最多放一條路徑

其中 $n$ 是節點數、h 是樹高（平衡樹 $O (\log n)$ 、斜樹 $O (n)$ ），都不含輸出的 res。

斜樹為什麼會退化：res = 左 + [自己] + 右 每一層都在建一個新的 list，把子樹的結果整份複製過去。左斜鏈的第 i 層要複製 i 個元素，加總起來就是 $1 + 2 + \dots + n = O (n^{2})$ 。