考的就是：中序遍历（非递归）

每次放子树全部子链进栈，每次遍历是取栈顶元素，删栈顶，将栈顶（之前删的栈顶）的右子树和右子树的左链进栈

图1：

图2：

把上述过程分拆到迭代器的函数里面

提示：
· next()和hasNext()操作的时间复杂度是$O(1)$，并使用$O(h)$ 内存，其中h是树的高度。
· 你可以假设next()调用总是有效的，也就是说，当调用 next()时，BST 中至少存在一个下一个最小的数。

算法分析

1. 二叉搜索树本身中序遍历后的元素是从小到大排序，因此找下一个最小的数，即在中序遍历中找当前元素的下一个元素

2. 中序遍历的过程：将整课树的最左边一条链压入栈中，每次取出栈顶元素，并记录栈顶元素，如果它有右子树，则将右子树压入栈中。

3. 此题是在中序遍历迭代手法的基础上进行拆分，首先先把整个左链键入到栈中，
   next()操作：当前pop()出的栈顶元素就是下一个最小的元素，为了维护中序遍历的序列，因此需要把pop()出的栈顶元素的右儿子的左链的所有元素加入到依次栈中
   hasNext()操作：判断栈是否有元素

class BSTIterator {
public:
    stack<TreeNode*> stk; //定义一个栈

    BSTIterator(TreeNode* root) { //要遍历当前子树，将当前子树左链全进栈，当根节点不空时
        while (root) {
            stk.push(root);
            root = root->left;
        }
    }

    int next() { //找下一个点，下一个点就是栈顶元素
        auto root = stk.top(); //取栈顶 并删掉栈顶
        int val = root->val; //返回值是栈顶元素 val 注意：这里不要写成stk.val 或stk->val
        stk.pop();
        root = root->right; //删完后把root的右子树和右子树的左链进栈
        while (root) {
            stk.push(root);
            root = root->left;
        }
        return val;
    }

    bool hasNext() { //只要栈不空，则遍历下一个点 进入next()
        return stk.size();
    }
};

/
* 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();
/