标准中序遍历法

时间复杂度：$O(n)$

空间复杂度：$O(n)$

能AC，但是达不到题目要求的 $O(h)$ 空间复杂度。

class BSTIterator {
public:
    vector<int> res;
    int t = 0;

    void inorder(TreeNode* root)
    {
        if (!root) return;

        inorder(root->left);
        res.push_back(root->val);
        inorder(root->right);
    }

    BSTIterator(TreeNode* root) {
        inorder(root);              //实例化时构造中序遍历数组
    }

    int next() {
        return res[t ++ ];          //t作为指针指向下一个节点
    }

    bool hasNext() {
        return t < res.size();
    }
};

用栈来中序遍历

时间复杂度：$O(n)$

空间复杂度：$O(h)$

栈中只存放根节点及其左子树的左节点，所以栈元素个数最多为二叉树的高度h，即空间复杂度为$O(h)$。

class BSTIterator {
public:
    stack<TreeNode*> stk;                   //栈中只存放根节点及其左子树的左节点

    void inorder(TreeNode* root)
    {
        while (root)
        {
            stk.push(root);
            root = root->left;
        }
    }

    BSTIterator(TreeNode* root) {
        inorder(root);
    }

    int next() {
        TreeNode* t = stk.top();            //取出栈顶节点
        stk.pop();

        if (t->right) inorder(t->right);    //回退的同时遍历该节点右子树

        return t->val;
    }

    bool hasNext() {
        return !stk.empty();                //栈不为空说明还有下一个节点
    }
};