題目描述:給定一棵二元樹的根節點 root,返回其節點值的後序遍歷(postorder traversal)結果。後序遍歷的順序是:左子樹 → 右子樹 → 根節點。
解題思路:後序遍歷的迭代實作比前序更複雜,因為根節點必須最後輸出。常見技巧是:觀察後序遍歷(左→右→根)恰好是「根→右→左」的逆序,而「根→右→左」與前序遍歷(根→左→右)結構相同,只是左右互換。
因此可以用一個類似前序的迭代(先推左子節點,再推右子節點),收集「根→右→左」序列,最後將結果反轉,即得後序遍歷。這個方法直觀、程式碼簡短,只需在前序模板上做兩處修改:推入順序左右對調,以及最後 reverse 結果。
時間複雜度: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),無需反轉,但實作邏輯較繁瑣。