LeetCode BST 迭代器：非遞歸中序遍歷的 O(1) 平均時間實現

LeetCode「二叉搜索樹迭代器」要求實現 next() 和 hasNext()，平均 O(1) 時間、O(h) 空間（h 為樹高）。本文解析基於顯式棧模擬中序遍歷的標準解法，並說明為什麼這是面試高頻考點。

問題分析

• BST 中序遍歷 = 遞增序列。
• next() 返回下一個最小值 → 即中序遍歷的下一個節點。
• 約束：平均 O(1) 時間、O(h) 空間 → 不能預先遍歷存入數組（那將是 O(n) 空間）。
• 必須惰性生成：只在調用 next() 時展開必要的節點。

核心算法：棧模擬遞歸

初始化：壓入左鏈

從根節點出發，沿左子節點不斷入棧，直到最左葉節點。棧頂即為最小值節點。

BSTIterator(TreeNode* root) {
    while (root) {
        st.push(root);
        root = root->left;
    }
}

hasNext()：檢查棧非空

bool hasNext() {
    return !st.empty();
}

next()：彈出棧頂，處理右子樹

1. 彈出棧頂節點 cur，其值即為返回值。
2. 若 cur->right 存在，將其作為新根，重複「壓入左鏈」過程：沿右子節點的左鏈入棧。
3. 返回 cur->val。

int next() {
    TreeNode* cur = st.top(); st.pop();
    if (cur->right) {
        TreeNode* p = cur->right;
        while (p) {
            st.push(p);
            p = p->left;
        }
    }
    return cur->val;
}

完整代碼（C++）

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

複雜度證明

• 空間：棧中最多存一條從根到葉的路徑 → O(h)。
• 時間：每個節點入棧一次、出棧一次。n 次 next() 總操作數 2n → 攤還 O(1)。

變體：Java 實現

class BSTIterator {
    Deque<TreeNode> stack = new ArrayDeque<>();
    public BSTIterator(TreeNode root) { pushLeft(root); }
    private void pushLeft(TreeNode node) {
        while (node != null) { stack.push(node); node = node.left; }
    }
    public boolean hasNext() { return !stack.isEmpty(); }
    public int next() {
        TreeNode cur = stack.pop();
        if (cur.right != null) pushLeft(cur.right);
        return cur.val;
    }
}

常見面試延伸

1. 前序/後序迭代器：同理可用棧模擬，但邏輯更複雜（需標記訪問狀態）。
2. 線程安全迭代器：若樹可被修改，需考慮快照或版本號機制。
3. Morris 遍歷：O(1) 空間（利用線索樹），但會修改樹結構，面試中可作為加分項討論。

總結

BST 迭代器是「棧模擬遞歸」的教科書級應用。關鍵洞察：中序遍歷的下一個節點 = 當前節點右子樹的最左節點（若存在），否則是祖先鏈中第一個當前節點在其左子樹中的祖先。棧自然維護了這條祖先鏈。掌握此模板，可舉一反三解決所有樹的非遞歸遍歷問題。