173.二叉搜索树迭代器

两天宇宙人

2020-02-21

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        stack<TreeNode*> stk;
        while(stk.size() || root) {
            while(root) {
                stk.push(root);
                root = root->left;
            }
            auto top = stk.top();
            stk.pop();
            vals.push_back(top->val);
            root = top->right;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        return vals[i++];
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return i != vals.size();
    }   
private:
    vector<int> vals;
    int i = 0;
};