LeetCode Binary Search Tree Iterator：中序遍歷迭代器實現

問題要求

實現 BST 迭代器，支持 next() 返回下一個最小值，hasNext() 判斷是否有下一個。要求均攤 O(1) 時間，O(h) 空間 (h 為樹高)。

棧模擬中序遍歷

中序遍歷 BST 即為升序輸出。用棧維护從根到當前最小節點的路徑：

• 構造函數：沿左子鏈入棧
• next()：彈出棧頂 (最小)，將其右子樹的左鏈入棧
• hasNext()：棧非空即有下一個

完整代碼

class BSTIterator {
    stack<TreeNode*> stk;
    void pushLeft(TreeNode* node) {
        while (node) {
            stk.push(node);
            node = node->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    bool hasNext() { return !stk.empty(); }
    int next() {
        TreeNode* cur = stk.top(); stk.pop();
        pushLeft(cur->right);
        return cur->val;
    }
};

複雜度分析

• 每個節點入棧出棧各一次 → 總時間 O(N)，均攤 O(1)
• 棧深度最大為樹高 h → 空間 O(h)

關鍵點

1. 將「找下一個」拆解為：輸出當前最小 + 為右子樹準備下一輪最小
2. pushLeft 封裝重複邏輯，構造函數與 next() 復用
3. 無需額外 visited 標記，BST 性質保證不重不漏

此題是「棧模擬遞歸」的教科書級應用，理解中序遍歷的棧幀變化是關鍵。