Description
實作一個 BST 的迭代器類別，初始化時指向 BST 中最小的元素之前。
next()回傳下一個最小的數，hasNext()回傳是否還有下一個數。要求平均 O(1) 時間、O(h) 空間。
Example:
Input: [“BSTIterator”,“next”,“next”,“hasNext”,“next”,“hasNext”,“next”,“hasNext”,“next”,“hasNext”] > [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]] Output: [null,3,7,true,9,true,15,true,20,false]
Intuition#
用堆疊模擬中序遍歷的暫停與恢復，每次 next() 推進一步。
- BST 中序遍歷產生遞增序列
- 迭代式中序遍歷用堆疊模擬，可以隨時暫停
- 初始化時將所有左子節點推入堆疊，next() 時彈出並轉向右子樹
Approaches#
1: 預先收集所有元素#
- 概念: 初始化時完整中序遍歷，結果存入列表，用指標遍歷
- 時間複雜度: next()
O(1)，初始化O(n) - 空間複雜度:
O(n)
class BSTIterator(root: TreeNode?) {
private val list = mutableListOf<Int>()
private var index = 0
init {
inorder(root)
}
private fun inorder(node: TreeNode?) {
if (node == null) return
inorder(node.left)
list.add(node.`val`)
inorder(node.right)
}
fun next(): Int = list[index++]
fun hasNext(): Boolean = index < list.size
}⭐ 2: 受控式中序遍歷（堆疊）#
- 概念: 用堆疊維護從當前節點到最左的路徑，next() 時彈出最小值並處理右子樹
- 時間複雜度: next() 平均
O(1)（攤提分析），hasNext()O(1) - 空間複雜度:
O(h)，h 為樹高
class BSTIterator(root: TreeNode?) {
private val stack = ArrayDeque<TreeNode>()
init {
pushAllLeft(root)
}
fun next(): Int {
val node = stack.removeLast()
pushAllLeft(node.right)
return node.`val`
}
fun hasNext(): Boolean = stack.isNotEmpty()
private fun pushAllLeft(node: TreeNode?) {
var curr = node
while (curr != null) {
stack.addLast(curr)
curr = curr.left
}
}
}為什麼 next() 的平均時間是 O(1)？
雖然單次 next() 可能需要 pushAllLeft 走過多個節點（最壞 O(h)），但每個節點在整個遍歷過程中只被推入和彈出堆疊各一次。n 次 next() 總共的操作是 O(n)，所以平均每次是 O(1)。這是典型的攤提分析。
🔑 Takeaways#
- Pattern: 用堆疊模擬中序遍歷的「暫停與恢復」，是 BST 迭代器的經典實作
- 關鍵技巧: pushAllLeft 函數是核心——確保堆疊頂端永遠是當前最小值，空間只需 O(h)