173. Binary Search Tree Iterator

題目 / Problem

中文： 實作一個 BSTIterator 類別，它是二元搜尋樹（BST）中序走訪的迭代器。指標一開始被放在「一個比樹中任何元素都小、且實際不存在的數」的位置，所以第一次呼叫 next() 會回傳最小的元素。

• BSTIterator(TreeNode root)：用 BST 的根節點初始化迭代器。
• boolean hasNext()：如果指標右邊還有數字（還沒走完），回傳 true，否則 false。
• int next()：把指標往右移一格，然後回傳指標所在的數字。

English: Implement a BSTIterator class that iterates over the in-order traversal of a binary search tree (BST). The pointer starts at a conceptual, non-existent number smaller than every element, so the first next() returns the smallest value.

• BSTIterator(TreeNode root): initialize the iterator with the BST root.
• boolean hasNext(): return true if a number still remains to the right of the pointer.
• int next(): move the pointer one step right, then return that number.

Constraints / 限制條件： - 節點數量在 [1, 10^5]。/ Number of nodes is in [1, 10^5]. - 0 <= Node.val <= 10^6。 - 最多 10^5 次 hasNext 與 next 呼叫。/ At most 10^5 calls total.

Worked Example / 範例： Tree [7, 3, 15, null, null, 9, 20]:

        7
       / \
      3   15
         /  \
        9    20

In-order traversal (中序序列) = 3, 7, 9, 15, 20. Calls: next→3, next→7, hasNext→true, next→9, hasNext→true, next→15, hasNext→true, next→20, hasNext→false.

名詞解釋 / Glossary

• 二元搜尋樹 / Binary Search Tree (BST): 一種二元樹，每個節點的左子樹所有值都比它小、右子樹所有值都比它大。/ A binary tree where every node's left subtree holds smaller values and its right subtree holds larger values.
• 中序走訪 / In-order traversal (LNR): 先走左子樹 → 再訪問自己 → 再走右子樹的順序。對 BST 來說，這個順序剛好是「由小到大排序」。/ Visit Left subtree → Node → Right subtree. For a BST this yields values in sorted ascending order.
• 迭代器 / Iterator: 一個可以「一次吐一個元素」的物件，記住目前走到哪裡，不需要一次把所有東西攤開。/ An object that yields elements one at a time, remembering its current position instead of materializing everything at once.
• 堆疊 / Stack: 一種「後進先出（LIFO）」的容器，只能從頂端 push（放入）和 pop（取出）。/ A Last-In-First-Out container; you push onto the top and pop from the top.
• 樹高 / Height (h): 從根到最深葉子的邊數。用堆疊模擬走訪時，堆疊最多存 h 個節點。/ The number of edges on the longest root-to-leaf path; our stack holds at most h nodes.
• 指標 / Pointer: 在 C/C++ 中儲存「某個變數在記憶體位址」的變數；node->val 表示透過指標存取節點的值。/ A variable holding a memory address; node->val reads a field through that address.
• 攤平 (預先展開) / Flatten (precompute): 暴力法會先把整棵樹中序走訪一遍存進陣列。/ The brute-force approach walks the whole tree once and stores the in-order sequence in an array.

思路

中文：最直覺的暴力法是——在建構子裡就把整棵樹做一次完整的中序走訪，把結果存進一個陣列，再用一個索引 i 當指標。next() 回傳 arr[i++]，hasNext() 檢查 i < 陣列長度。這樣完全正確，而且 next/hasNext 都是 O(1)。它的缺點是空間：必須一開始就存下全部 n 個節點，也就是 O(n) 記憶體。題目的 follow-up 希望我們只用 O(h)（樹高）的記憶體。

要省記憶體，關鍵觀察是：中序走訪其實可以「用一個堆疊來延遲展開」。我們不需要一開始就走完整棵樹，只要隨時保證堆疊裡放著「接下來即將被訪問的節點鏈」。做法是定義一個輔助動作 pushLeft(node)：從 node 開始，沿著左子鏈一路往下，把每個節點都 push 進堆疊，直到沒有左子。這樣堆疊頂端永遠是「目前尚未訪問的最小節點」。建構子只對 root 做一次 pushLeft。next() 時，pop 出堆疊頂端 cur（它就是下一個中序值），然後對 cur->right 做一次 pushLeft——因為在中序裡，訪問完一個節點後，下一步就是進到它的右子樹再找最左。hasNext() 只要看堆疊是不是空的。堆疊最多同時裝著一條根到某節點的左鏈，長度不超過樹高 h，所以空間是 O(h)。每個節點一生只會被 push、pop 各一次，總共 2n 次操作攤分到 n 次 next，所以 next 平均是 O(1)。

English: The most obvious brute force is to do one full in-order traversal inside the constructor, store the sorted values in an array, and keep an index i. Then next() returns arr[i++] and hasNext() checks i < length. This is correct and both operations are O(1), but it costs O(n) memory because it holds every node up front. The follow-up asks for O(h) memory instead, where h is the tree height.

The trick is that in-order traversal can be lazily driven by a stack. We never expand the whole tree at once; instead we maintain the invariant that the stack always contains the chain of not-yet-visited ancestors whose top is the next node to emit. Define a helper pushLeft(node) that walks down the left spine from node, pushing every node until there is no left child — this leaves the smallest unvisited node on top. The constructor calls pushLeft(root) once. In next(), we pop the top node cur (the next in-order value) and then call pushLeft(cur->right), because in in-order order the successor of a node lives in the leftmost part of its right subtree. hasNext() just checks whether the stack is non-empty. Since the stack only ever holds one left-spine at a time, its size is bounded by the height h, giving O(h) space. Each node is pushed and popped exactly once over the iterator's whole life, so across n calls the amortized cost of next() is O(1).

逐步走查 / Walkthrough

Tree: root 7, left 3, right 15 (with 15's children 9 and 20). Expected in-order: 3, 7, 9, 15, 20.

Notation: stack shown bottom→top.

Notice the stack never held more than 2 nodes — bounded by the tree height, not the node count. / 注意堆疊最多只裝 2 個節點，受限於樹高而非節點總數。

Solution — C

/*
 * 演算法 / Algorithm:
 * 用一個堆疊延遲進行中序走訪。pushLeft 把某節點及其整條左子鏈壓入堆疊，
 * 讓堆疊頂端永遠是下一個要訪問的最小節點。next() pop 頂端並對其右子做 pushLeft。
 * We drive an in-order traversal lazily with a stack: pushLeft pushes a node and
 * its entire left spine so the top is always the next value; next() pops it and
 * pushLeft's its right child. Space O(h), amortized O(1) per next().
 */

// LeetCode 已定義 struct TreeNode（含 val、left、right）/ TreeNode is predefined by LeetCode.

typedef struct {
    struct TreeNode** stack; // 存節點指標的動態陣列，當作堆疊 / dynamic array of node pointers used as a stack
    int top;                 // 堆疊頂端索引：-1 表示空 / index of top element; -1 means empty
} BSTIterator;

// 輔助函式：從 node 開始，沿左子鏈全部壓入堆疊 / Helper: push node and its whole left spine.
void pushLeft(BSTIterator* it, struct TreeNode* node) {
    while (node != NULL) {          // 只要還有節點就繼續往左 / keep going while a node exists
        it->top++;                  // 頂端上移一格，指向新的寫入位置 / advance top to the next slot
        it->stack[it->top] = node;  // 把目前節點存入堆疊頂端 / store current node on top
        node = node->left;          // 移到左子，準備下一次壓入 / descend to the left child
    }
}

BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
    // malloc 配置一塊 BSTIterator 大小的記憶體，回傳其指標 / allocate the iterator struct
    BSTIterator* it = (BSTIterator*)malloc(sizeof(BSTIterator));
    // 最多 10^5 個節點，配置足夠大的陣列當堆疊 / stack big enough for up to 1e5 nodes
    it->stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100000);
    it->top = -1;                   // 一開始堆疊為空 / start empty
    pushLeft(it, root);             // 建構時先壓入根的左子鏈 / seed with root's left spine
    return it;
}

int bSTIteratorNext(BSTIterator* it) {
    // 取出堆疊頂端節點：它就是下一個中序值 / pop the top node = next in-order value
    struct TreeNode* cur = it->stack[it->top];
    it->top--;                      // 頂端下移，等於彈出 / move top down = pop
    // 中序後繼在右子樹的最左處，故對右子做 pushLeft / successor is leftmost of right subtree
    pushLeft(it, cur->right);
    return cur->val;                // 回傳該節點的值 / return the popped node's value
}

bool bSTIteratorHasNext(BSTIterator* it) {
    return it->top >= 0;            // 頂端 >= 0 代表堆疊還有元素 / non-empty iff top >= 0
}

void bSTIteratorFree(BSTIterator* it) {
    free(it->stack);                // 先釋放內部陣列，避免記憶體洩漏 / free inner array first
    free(it);                       // 再釋放結構本身 / then free the struct
}

/**
 * 使用方式 / Usage:
 * BSTIterator* obj = bSTIteratorCreate(root);
 * int param_1 = bSTIteratorNext(obj);
 * bool param_2 = bSTIteratorHasNext(obj);
 * bSTIteratorFree(obj);
 */

Solution — C++

/*
 * 演算法 / Algorithm:
 * 用 std::stack 延遲中序走訪。pushLeft 壓入一個節點及其整條左子鏈，
 * 使堆疊頂端永遠是下一個中序節點。next() 取頂端並對其右子 pushLeft。
 * Lazy in-order traversal with a stack: pushLeft loads a node's left spine so the
 * top is the next value; next() pops it and pushLeft's its right child.
 * Space O(h), amortized O(1) per next().
 */

#include <stack>

// TreeNode 由 LeetCode 預先定義 / TreeNode is predefined by LeetCode.

class BSTIterator {
private:
    // std::stack 是後進先出容器；這裡存節點指標 / a LIFO container of node pointers
    std::stack<TreeNode*> st;

    // 把 node 及其整條左子鏈壓入堆疊 / push node and its entire left spine
    void pushLeft(TreeNode* node) {
        while (node != nullptr) {   // while 迴圈沿左子一路下走 / walk down the left children
            st.push(node);          // 壓入目前節點 / push current node onto the stack
            node = node->left;      // 移到左子 / move to the left child
        }
    }

public:
    // 建構子：初始化時壓入根的左子鏈 / constructor seeds root's left spine
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }

    int next() {
        TreeNode* cur = st.top();   // 讀取頂端節點：下一個中序值 / peek the next in-order node
        st.pop();                   // 彈出它 / remove it from the stack
        pushLeft(cur->right);       // 後繼在右子樹最左處 / successor lives in the right subtree
        return cur->val;            // 回傳其值 / return its value
    }

    bool hasNext() {
        return !st.empty();         // 堆疊非空就還有下一個 / more remain iff stack is non-empty
    }
};

/**
 * 使用方式 / Usage:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

複雜度 / Complexity

• Time / 時間: hasNext() 是 O(1)。next() 單次最壞是 O(h)（要沿右子樹的左鏈往下），但每個節點一生只被 push 與 pop 各一次，總工作量 O(n) 攤分到 n 次 next，因此攤還 O(1)。/ hasNext() is O(1). A single next() is O(h) worst case, but each node is pushed/popped exactly once, so across all calls the total is O(n), giving amortized O(1) per next().
• Space / 空間: O(h)。堆疊在任一時刻只裝著一條由根到某節點的左鏈，其長度不超過樹高 h。相較暴力法的 O(n) 大幅節省（尤其在平衡樹中 h ≈ log n）。/ O(h): the stack only ever holds one root-to-node left spine, bounded by the height h. Much better than the brute-force O(n), especially for a balanced tree where h ≈ log n.

Pitfalls & Edge Cases

• 不要一開始就攤平整棵樹 / Don't flatten upfront: 把整個中序序列存陣列雖然正確，但用 O(n) 空間，過不了 follow-up 的 O(h) 要求。堆疊做法才符合。/ Precomputing the full array works but uses O(n) space and misses the O(h) follow-up.
• pushLeft(node->right) 傳入 null 是安全的 / Passing null to pushLeft is safe: 當節點沒有右子時傳入 NULL/nullptr，while 迴圈條件立刻為假、什麼都不做，不會崩潰。這正是葉節點能正確運作的原因。/ A null right child just makes the while loop skip; no crash. This is why leaves work correctly.
• 只能 pop 一次 / Pop exactly once per next: next() 必須先取頂端再 pop，順序弄反或忘記 pop 會重複回傳同一值或跳過。C++ 中 st.top() 只是「看」，st.pop() 才是「移除」，兩者要成對。/ In C++, top() peeks and pop() removes — you need both; forgetting pop() repeats a value.
• 空樹 / Empty tree: 本題保證至少 1 個節點，但程式仍安全——pushLeft(NULL) 不壓任何東西，hasNext() 立刻回傳 false。/ Constraints guarantee ≥1 node, yet the code is still safe: pushLeft(null) pushes nothing and hasNext() returns false.
• C 版記憶體 / C memory management: 用完要呼叫 bSTIteratorFree 釋放 stack 陣列與結構本身，否則記憶體洩漏。這裡用固定大小 100000 是因為節點上限已知；動態成長也可以但較複雜。/ Free both the inner array and the struct to avoid leaks; the fixed 1e5 size is safe because the node count is bounded.
• 值域無溢位風險 / No overflow risk: Node.val 最大 10^6，遠在 int 範圍內，回傳值不需特別處理。/ Values fit comfortably in int, so returns need no special handling.