173. Binary Search Tree Iterator

發表於 | 分類於

problem

solution

option 1 - STL to store

事先先拜訪過各節點並存下來，再用一個指標指向當前位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BSTIterator {
private:
    vector<int> nums;
    int cur =0;
public:
    BSTIterator(TreeNode* root) {
        preorder(root);
        
    }
    void preorder(TreeNode *root){
        if(!root) return;
        preorder(root->left);
        nums.push_back(root->val);
        preorder(root->right);
    }
    int next() {
        return nums[cur++];
    }
    
    bool hasNext() {
        return cur!=nums.size();
    }
};

option 2 - stack

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
28
29
30
31
class BSTIterator {
private:
    stack<TreeNode *>sta;
public:
    BSTIterator(TreeNode* root) {
        while(root){
            sta.push(root);
            root= root->left;
        }
    }
    
    int next() {
        TreeNode * p = sta.top();
        sta.pop();
        int ret = p->val;
        // 以p 為樹根 左半部已經拜訪完畢
        // 從右子樹找下一個拜訪的點，並放入stack
        if(p->right){
            p=p->right;
            while(p){
                sta.push(p);
                p=p->left;
            }
        }
        return ret;
    }
    
    bool hasNext() {
        return !sta.empty();
    }
};

analysis

  • time complexity O(1)
  • space complexity O(h)