題目描述：實作一個 BST 的迭代器，支援兩個操作：next() 回傳 BST 中下一個最小的整數，hasNext() 回傳是否還有下一個元素。要求 next() 和 hasNext() 的平均時間複雜度為 O(1)，並且只使用 O(h) 的額外空間（h 為樹的高度）。
解題思路：BST 的中序遍歷（左→根→右）產生的序列恰好是升序排列。若完整展開中序遍歷並儲存結果，空間為 O(n)，不符合 O(h) 的要求。
關鍵觀察：中序遍歷的本質是「先走到最左端，處理後再去右子樹，右子樹又重複相同步驟」。用一個顯式的堆疊（stack）模擬這個過程：
next()：彈出堆疊頂端節點（即當前最小值），若該節點有右子節點，則將右子節點及其左側鏈全部壓入堆疊（為下一次 next() 做準備）。回傳彈出節點的值。hasNext()：只需檢查堆疊是否非空。堆疊在任何時刻最多存放 O(h) 個節點（當前路徑上的左側鏈），符合空間要求。雖然每次 next() 在最壞情況下可能壓入 O(h) 個節點，但均攤分析下每個節點恰好被壓入和彈出一次，所以 next() 的均攤時間複雜度為 O(1)。
時間複雜度：O(1) 均攤（amortized）— 每個節點在整個迭代過程中恰好被壓入堆疊一次、彈出一次，因此 n 次 next() 呼叫共執行 O(n) 次堆疊操作，均攤每次 O(1)。hasNext() 每次嚴格 O(1)。
空間複雜度：O(h) — 堆疊中同時存放的節點為當前路徑上的左側鏈，最多 h 個節點（h 為樹的高度）。平衡 BST 下 h = O(log n)，退化樹下 h = O(n)。
1. Constructor(root):
a. Initialize an empty stack
b. Call pushLeft(root) to push all left-spine nodes onto the stack
2. pushLeft(node):
a. While node is not null:
- Push node onto stack
- Move to node.left
3. next():
a. Pop the top node from the stack
b. Call pushLeft(node.right) to prepare the next sequence
c. Return node.val
4. hasNext():
a. Return true if stack is non-empty, false otherwise方法一：預先完整展開中序遍歷
在建構子中對整棵樹做一次完整的中序遍歷，將所有值依序存入一個陣列，再用一個索引指標追蹤當前位置。next() 直接回傳索引處的值並遞增索引，hasNext() 檢查索引是否越界。實作最簡單，next() 和 hasNext() 均嚴格 O(1)，但空間複雜度為 O(n)，不符合題目 O(h) 的空間限制。
方法二：Morris 中序遍歷（無額外空間）
Morris 遍歷利用葉節點多餘的 nullptr 指標暫時建立「線索」（thread），以 O(1) 額外空間完成中序遍歷，不需要堆疊。但這種方法會暫時修改樹的結構（在取值後再還原），對於需要並發讀取或樹為唯讀場景不適用，且實作較為複雜。時間複雜度 O(1) 均攤，空間複雜度 O(1)。
prev()（回傳前一個最大值）的雙向 BST 迭代器，你會如何修改設計？需要幾個堆疊？next() 均攤 O(1)，但某次呼叫可能需要 O(h) 時間。在實時系統（real-time system）中，這種最壞情況的延遲是否可以接受？如何設計才能讓每次呼叫嚴格 O(1)？