給定一棵 BST 的根節點和整數 k，回傳 BST 中第 k 小的元素（1-indexed）。
Example:
Input: root = [3,1,4,null,2], k = 1 Output: 1
Intuition
TIP
BST 中序遍歷是有序的，第 k 個被訪問的節點就是答案。
- 中序遍歷 BST 得到遞增序列，遍歷到第 k 個就可以提前停止
- 不需要真的收集所有元素，用計數器即可
Approaches
1. Inorder to Collect All — O(n) / O(n)
- Idea: 完整中序遍歷收集所有值到列表，回傳第 k-1 個元素
- Time:
O(n) - Space:
O(n)
class Solution {
fun kthSmallest(root: TreeNode?, k: Int): Int {
val list = mutableListOf<Int>()
inorder(root, list)
return list[k - 1]
}
private fun inorder(node: TreeNode?, list: MutableList<Int>) {
if (node == null) return
inorder(node.left, list)
list.add(node.`val`)
inorder(node.right, list)
}
}⭐ 2. Inorder + Early Stop (iterative) — O(h + k) / O(h)
- Idea: 迭代式中序遍歷，計數到 k 就立即回傳
- Time:
O(h + k)，h 為樹高 - Space:
O(h)
class Solution {
fun kthSmallest(root: TreeNode?, k: Int): Int {
val stack = ArrayDeque<TreeNode>()
var current = root
var count = 0
while (current != null || stack.isNotEmpty()) {
while (current != null) {
stack.addLast(current)
current = current.left
}
current = stack.removeLast()
count++
if (count == k) return current.`val`
current = current.right
}
return -1 // 不會到達
}
}Iterative Inorder Traversal Template
迭代式中序遍歷的核心模式：
- 先一路往左走到底，把沿途節點推入堆疊
- 彈出堆疊頂端（當前最小未處理節點）
- 處理該節點
- 轉向右子樹，重複步驟 1
這個模板可以用在很多 BST 問題上。
🔑 Takeaways
- Pattern: BST + 中序遍歷 = 有序序列，第 k 小/大問題直接解決
- Key trick: 迭代式中序遍歷可以在找到答案後提前停止，比遞迴更容易控制提前終止