Binary Search Tree Iterator

Binary Search Tree Iterator.png

解題思路 ：

兩種做法:

1. 直接把所有 node 依照 inorder 順序存入 vector 然後設定一個 index 的紀錄點即可
2. 利用 stack 一路存入 left child 然後每次 pop 一個 node 就用此 node 的 right child 為起點再繼續存入所有 left child

C++ code :

<pre><code>
//solution 1: using vector

class BSTIterator {

public:

//@param root: The root of binary tree.

vector<TreeNode*> v;
int pos = 0;

BSTIterator(TreeNode *root) {
    init(root);
}

void init(TreeNode* root)
{
    if(root)
    {
        init(root->left);
        v.emplace_back(root);
        init(root->right);
    }
}

/** @return whether we have a next smallest number */
bool hasNext() {
    return pos < int(v.size());
}

/** @return the next smallest number */
TreeNode* next() {
    return v[pos++];
}

};

//solution 2: using stack
class BSTIterator {

public:

//@param root: The root of binary tree.
stack<TreeNode*> s;
TreeNode *cur;
BSTIterator(TreeNode *root) {
    cur = root;
    while(cur)
    {
        s.push(cur);
        cur = cur->left;
    }
}

/** @return whether we have a next smallest number */
bool hasNext() {
    return !s.empty() || cur;
}

/** @return the next smallest number */
TreeNode* next() {
    TreeNode *tmp = s.top();
    s.pop();
    if(tmp->right){
        cur = tmp->right;
        while(cur)
        {
            s.push(cur);
            cur = cur->left;
        }
    }
    return tmp;
}

};