給定一棵二元樹的根節點，回傳其後序遍歷 (Postorder Traversal) 的節點值列表。後序遍歷順序為：左子樹 -> 右子樹 -> 根。
Example:
Input: root = [1,null,2,3] Output: [3,2,1]
Intuition
TIP
後序遍歷：先遞迴走左、右子樹，最後才處理當前節點。
- 後序遍歷順序為 Left -> Right -> Root
- 迭代版本可以利用「反轉的前序遍歷」技巧：前序是 Root -> Left -> Right，改為 Root -> Right -> Left 後反轉即得 Left -> Right -> Root
Approaches
1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴先走左子樹，再走右子樹，最後處理當前節點
- Time:
O(n) - Space:
O(h)
class Solution {
fun postorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
fun dfs(node: TreeNode?) {
if (node == null) return
dfs(node.left)
dfs(node.right)
result.add(node.`val`)
}
dfs(root)
return result
}
}⭐ 2. Iterative (reverse preorder) — O(n) / O(n)
- Idea: 修改前序遍歷為 Root -> Right -> Left，最後將結果反轉即為後序遍歷
- Time:
O(n) - Space:
O(n)，需要存放完整結果後反轉
class Solution {
fun postorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
if (root == null) return result
val stack = ArrayDeque<TreeNode>()
stack.addLast(root)
while (stack.isNotEmpty()) {
val node = stack.removeLast()
result.add(node.`val`)
node.left?.let { stack.addLast(it) }
node.right?.let { stack.addLast(it) }
}
return result.reversed()
}
}🔑 Takeaways
- Pattern: 樹的遍歷 — 後序遍歷常用於需要先處理子樹再處理父節點的場景（如刪除樹、計算子樹大小）
- Key trick: 迭代後序遍歷可以透過「修改前序 + 反轉」的技巧簡化實作，避免複雜的雙棧或標記法