原题描述

二叉搜索树迭代器

思路

模拟法。 用O(n)空间的数组保存中序遍历的结果，使用指针start保存当前迭代器所处的下标。

class BSTIterator {
public:
    vector<int> vals;
    int len = 0;
    int start = -1;

    void _build(TreeNode* root) {
        if (!root) return;
        if (root->left) _build(root->left);
        vals.push_back(root->val);
        ++len;
        if (root->right) _build(root->right);
    }

    BSTIterator(TreeNode* root) {
        _build(root);
    }
    
    int next() {
        return vals[++start];
    }
    
    bool hasNext() {
        return start + 1 < len;
    }
};

运行结果

执行用时：28 ms, 击败 91.85% 的用户
内存消耗：23.6 MB，超过 45.59% 的用户