Leetcode 173: binary search iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

这道题要求输出是从最小的number 到最大，其实对于binary search tree来说就是inorder的遍历，题目转化为写inorder的iterator，

tree的Inorder遍历维护一个stack，最初stack里面存从root到最左node的路径，并且可以获得最小值，在返回最小值前，把cur 指向right，下次调用的时候，如果right不为空，那么right push到stack中，否则直接将stack上的top返回，即没有right节点的时候，root是次大的。

class BSTIterator {
private:
    stack<TreeNode*> buf;
    TreeNode* cur;
public:
    BSTIterator(TreeNode *root) {
       cur = root;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        if (buf.empty() && cur == NULL) return false;
        return true;
    }

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