---
title: "145. Binary Tree Postorder Traversal"
url: "https://laigary.com/interview/coding/145-binary-tree-postorder-traversal"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Tree", "Postorder Traversal"]
---

# 145. Binary Tree Postorder Traversal

[145\. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)

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

## 思路

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

> Recursive solution is trivial, could you do it iteratively?

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

但有一個很漂亮的繞路：

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

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

### 後序為什麼是樹的主力

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

- 最大深度 → 回傳子樹深度，取 `max + 1`（[104](/interview/coding/104-maximum-depth-of-binary-tree)）
- 直徑 → 回傳單邊最長，答案取左右相加（[543](/interview/coding/543-diameter-of-binary-tree)）
- 最大路徑和 → 同上，但要處理負數（[124](/interview/coding/124-binary-tree-maximum-path-sum)）
- 樹形 DP → 回傳「選 / 不選」兩種狀態（[337](/interview/coding/337-house-robber-iii)）

這一型的關鍵是**回傳給父節點的值，和答案要的值常常不一樣**（124 回傳單邊、答案取兩邊相加）。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 解題方向

### 遞迴

```python
# 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）：

```python
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：做「根右左」再反轉

```python
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. 前序](/interview/coding/144-binary-tree-preorder-traversal) 的 iterative 版比一比，只有兩處不同：**進棧的左右順序對調**、**最後多一個 `[::-1]`**。前序記住了，後序就是免費的。

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

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

## 補充

**四種遍歷一起看**：[144. 前序](/interview/coding/144-binary-tree-preorder-traversal)、[94. 中序](/interview/coding/94-binary-tree-inorder-traversal)、[145. 後序](/interview/coding/145-binary-tree-postorder-traversal)、[102. 層序](/interview/coding/102-binary-tree-level-order-traversal)。

**後序型的實戰題**：[104. Maximum Depth](/interview/coding/104-maximum-depth-of-binary-tree)、[543. Diameter of Binary Tree](/interview/coding/543-diameter-of-binary-tree)、[124. Binary Tree Maximum Path Sum](/interview/coding/124-binary-tree-maximum-path-sum)、[337. House Robber III](/interview/coding/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)$。