二叉搜尋樹中序周遊（從小到大輸出）的資料結構（利用棧）

173. Binary Search Tree Iterator

Medium

1309237FavoriteShare

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling ​

​next()​

​ will return the next smallest number in the BST.

Example:

class BSTIterator {
private:
    int NextMin;
    stack<TreeNode*> s;
public:
    BSTIterator(TreeNode* root) {
        if(root == NULL){return;}
        s.push(root);
        TreeNode* left = root->left;
        while(left){
            s.push(left);
            NextMin = left->val;
            left = left ->left;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        if(hasNext()){
            TreeNode* tmp = s.top();
            s.pop();
            NextMin = tmp->val;
            TreeNode* tmp1 = tmp->right;
            if(tmp1){
                s.push(tmp1);
                while(tmp1->left != NULL){
                    s.push(tmp1->left);
                    tmp1 = tmp1->left;
                }
            }
            return NextMin;
        }
        return -1;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(!s.empty()){
            return true;
        }
        return false;
    }
};