給定一棵二元樹的根節點，回傳其中序遍歷 (Inorder Traversal) 的節點值列表。中序遍歷順序為：左子樹 -> 根 -> 右子樹。
Example:
Input: root = [1,null,2,3] Output: [1,3,2]
Intuition
TIP
中序遍歷：先遞迴走左子樹，再處理當前節點，最後走右子樹。
- 中序遍歷是三種基本遍歷之一，順序為 Left -> Root -> Right
- 遞迴寫法最直覺，迭代寫法需要用 Stack 模擬遞迴過程
- 對 BST 做中序遍歷會得到排序結果
Approaches
1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴先走左子樹，再加入當前節點值，最後走右子樹
- Time:
O(n)，每個節點訪問一次 - Space:
O(h)，遞迴堆疊深度，h 為樹高
class Solution {
fun inorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
fun dfs(node: TreeNode?) {
if (node == null) return
dfs(node.left)
result.add(node.`val`)
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 inorderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
val stack = ArrayDeque<TreeNode>()
var curr = root
while (curr != null || stack.isNotEmpty()) {
while (curr != null) {
stack.addLast(curr)
curr = curr.left
}
curr = stack.removeLast()
result.add(curr.`val`)
curr = curr.right
}
return result
}
}🔑 Takeaways
- Pattern: 樹的遍歷 — 中序遍歷是 BST 相關問題的基礎
- Key trick: 迭代版本的核心是「一路向左壓棧，彈出時處理並轉右」，這個模式在很多樹的題目中都會用到