給定一棵二元樹的根節點，回傳其前序遍歷 (Preorder Traversal) 的節點值列表。前序遍歷順序為：根 -> 左子樹 -> 右子樹。
Example:
Input: root = [1,null,2,3] Output: [1,2,3]
Intuition
TIP
前序遍歷：先處理當前節點，再遞迴走左子樹，最後走右子樹。
- 前序遍歷順序為 Root -> Left -> Right
- 迭代版本用 Stack，注意先壓入右子節點再壓左子節點（因為 Stack 是 LIFO）
Approaches
1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴先處理當前節點，再依序走左、右子樹
- Time:
O(n) - Space:
O(h)
class Solution {
fun preorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
fun dfs(node: TreeNode?) {
if (node == null) return
result.add(node.`val`)
dfs(node.left)
dfs(node.right)
}
dfs(root)
return result
}
}⭐ 2. Iterative with Stack — O(n) / O(h)
- Idea: 用 Stack 模擬，彈出節點時處理，先壓右再壓左確保左先被處理
- Time:
O(n) - Space:
O(h)
class Solution {
fun preorderTraversal(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.right?.let { stack.addLast(it) }
node.left?.let { stack.addLast(it) }
}
return result
}
}🔑 Takeaways
- Pattern: 樹的遍歷 — 前序遍歷在序列化、複製樹等場景常用
- Key trick: 迭代前序遍歷的 Stack 中，先壓右再壓左，保證左子樹先被處理