LeetCode 173. Binary Search Tree Iterator

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class BSTIterator {
private:
    int idx;
    vector<int> v;
    vector<int> inorder(TreeNode *root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
    void inorder(TreeNode* root, vector<int>& v) {
        if (!root) return;
        inorder(root->left, v);
        v.emplace_back(root->val);
        inorder(root->right, v);
    }
public:
    BSTIterator(TreeNode* root): idx(0), v(inorder(root)) {
    }
    
    int next() {
        return v[idx++];
    }
    
    bool hasNext() {
        return idx < v.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BSTIterator {
private:
    TreeNode* curr;
    stack<TreeNode*> stk;
public:
    BSTIterator(TreeNode* root): curr(root) {
    }
    
    int next() {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top();
        stk.pop();
        int ans = curr->val;
        curr = curr->right;
        return ans;
    }
    
    bool hasNext() {
        return curr || !stk.empty();
    }
};