二叉树的中序遍历

由二叉搜索树中序遍历有序性。且中序遍历的顺序是：左根右。所以该题主要是对二叉树中序遍历代码的拆分。

1.初始化

• 初始化，我们先将根节点的左子树遍历，并且压入栈

2.next

• 因为是中序遍历，所以当前栈顶就是最小的元素
• 弹出后再将该节点向右，并且将左子树都遍历，压入栈

3.hasNext

• 栈中如果有节点，说明还没有遍历完
• 栈中如果没有节点，说明遍历完了

$ 时间复杂度O(N),空间复杂度O(N)$

参考文献

lc究极班

AC代码

/**
 * 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 {
public:
    stack<TreeNode*> stk;
    BSTIterator(TreeNode* root) {
        //根节点的左子树入栈
        while (root){
            stk.push(root);
            root = root->left;
        }
    }

    /** @return the next smallest number */
    int next() {
        //栈顶为最小元素
        auto root = stk.top();
        int v = root->val;
        stk.pop();
        //将栈顶的元素的转向右边
        root = root->right;
        //左子树全入栈
        while (root){
            stk.push(root);
            root = root->left;
        }
        return v;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        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();
 */