1586.md

1586. 二叉搜索树迭代器II

解题思路

解法1：非进阶，直接用一个数组中序遍历收集所有的元素。然后根据index的范围判断是否存在前驱或者后继。基本思路就是直接++index，--index（有些细节需要读者直接尝试）访问提前收集的数组即可。

解法2：进阶解法。要借用中序遍历的栈和一个vector list保存已经遍历过的元素。这样查找前驱可以直接再list里面找，如果找到就有，list为空就没有前驱。后继跟普通的没有查找前驱的173题不一样。由于我们有可能已经前移获取过前驱了。因此后继有可能已经序列化到了栈中，并且存储到了list中，我们要先看看是否list已有该后继，有的话，直接返回。没有的话，再跟以前的173题一样，pop栈顶元素cur, pushLeft(cur->right)，保存cur到list，返回cur->val即可。

代码

class BSTIterator1 {
public:
    BSTIterator1(TreeNode* root) {
        inOrder(root, nums);
    }

    void inOrder(TreeNode* root, vector<int>& nums) {
        if (!root) {
            return;
        }

        inOrder(root->left, nums);
        nums.push_back(root->val);
        inOrder(root->right, nums);
    }
    
    bool hasNext() {
        return size < static_cast<int>(nums.size());
    }
    
    int next() {
        assert(hasNext());
        return nums[size++];
    }
    
    bool hasPrev() {
        return size > 1;
    }
    
    int prev() {
        assert(hasPrev());
        --size;
        return nums[size - 1];
    }

private:
    int size = 0;
    vector<int> nums;
};



 
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }

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

    bool isInRange(int i) {
        return i >= 0 && i < list.size();
    }

    bool hasNext() {
        if (isInRange(index + 1)) {
            return true;
        }

        return !stk.empty();
    }
    
    int next() {
        assert(hasNext());
        int curVal = 0;
        if (isInRange(index + 1)) {
            curVal = list[index + 1]->val;
        } else {
            auto cur = stk.top(); stk.pop();
            pushLeft(cur->right);
            list.push_back(cur);
            curVal = cur->val;
        }
        
        index++;
        return curVal;
    }
    
    bool hasPrev() {
        return isInRange(index - 1);
    }
    
    int prev() {
        --index;
        return list[index]->val;

    }

private:
    int index = -1;
    stack<TreeNode*> stk;
    vector<TreeNode*> list;
};