EasyRating 1214

145. Binary Tree Postorder Traversal

stacktreedepth-first-searchbinary-tree

在 LeetCode 上作答 ↗

解題說明

Binary Tree Postorder Traversal

題目描述：給定一棵二元樹的根節點 root，返回其節點值的後序遍歷（postorder traversal）結果。後序遍歷的順序是：左子樹 → 右子樹 → 根節點。

解題思路：後序遍歷的迭代實作比前序更複雜，因為根節點必須最後輸出。常見技巧是：觀察後序遍歷（左→右→根）恰好是「根→右→左」的逆序，而「根→右→左」與前序遍歷（根→左→右）結構相同，只是左右互換。

因此可以用一個類似前序的迭代（先推左子節點，再推右子節點），收集「根→右→左」序列，最後將結果反轉，即得後序遍歷。這個方法直觀、程式碼簡短，只需在前序模板上做兩處修改：推入順序左右對調，以及最後 reverse 結果。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點訪問一次（O(n)），加上最後的 reverse 操作也是 O(n)，整體仍為 O(n)。

空間複雜度：O(n) — 堆疊最多存放 O(n) 個節點（偏斜樹最壞情況），結果陣列也佔 O(n) 空間。

虛擬碼

1. If root is null, return empty list
2. Initialize stack with root, result as empty list
3. While stack is not empty:
   a. Pop node from stack
   b. Append node.val to result  (collecting root→right→left order)
   c. If node.left exists, push node.left onto stack
   d. If node.right exists, push node.right onto stack
4. Reverse result
5. Return result

其他解法

方法一：遞迴（Recursive DFS） 遞迴呼叫左子樹、右子樹，最後訪問當前節點。程式碼最簡潔，時間複雜度 O(n)，空間複雜度 O(n)（呼叫堆疊）。

方法二：雙堆疊法 使用兩個堆疊：第一個堆疊做「根→右→左」的遍歷，彈出時推入第二個堆疊；遍歷結束後依序彈出第二個堆疊即得後序結果。邏輯清晰，空間複雜度 O(n)，但使用了兩個堆疊。

方法三：單堆疊 + visited 標記 使用單一堆疊搭配 prev 指標追蹤上一個訪問的節點，判斷是否已處理完右子樹後才輸出根節點。空間複雜度 O(n)，無需反轉，但實作邏輯較繁瑣。

延伸思考

後序遍歷常用於「先處理子節點再處理父節點」的場景，能舉出一個實際應用範例嗎？（例如：刪除整棵樹、計算目錄大小）
如何利用後序遍歷和中序遍歷的結果，唯一重建原始二元樹？（LeetCode 106）
在「判斷二元樹是否為平衡樹」（LeetCode 110）的最優解中，為什麼選擇後序遍歷而非前序遍歷？