题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

 //这道题就是写一个中序遍历，因为题目提到是搜索二叉树
class BSTIterator {
    stack<TreeNode*> s;//在private里定义栈
public:
    BSTIterator(TreeNode* root) {
        while(root){
            s.push(root);
            root = root->left;
        }
    }//先把最左子树全部压入栈中
    
    /** @return the next smallest number */
    int next() {
        TreeNode* cur = s.top();s.pop();//取栈顶值
        int res = cur->val;//取值
        if(cur->right){
            cur = cur->right;
            while(cur){
                s.push(cur);
                cur = cur->left;
            }
        }//若其有右子树，将其右子树的全部最左子树压入栈中
        return res;//返回结果
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();//当栈不为空则hasNext,即有下一个值
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */