Binary Search Tree Iterator

题目：

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)

next() and hasNext() queries run in O(1) time in average.

接口：

class BSTIterator {
public:
    //@param root: The root of binary tree.
    BSTIterator(TreeNode *root) {
        // write your code here
    }

    //@return: True if there has next node, or false
    bool hasNext() {
        // write your code here
    }

    //@return: return next node
    TreeNode* next() {
        // write your code here
    }
};

分析：这是一道背诵题目啊~居然还是高频！

这题目需要用到一个stack一个TreeNode*，整体的逻辑就是在hasNext()中把所有左子树中的内容用inorder的顺序放到stack里面。

具体要注意的地方有三个

(1) 构造函数时候确定stack为空

(2) 首先判断curr是不是NULL， 然后判断S是否为empty

(3) 把curr左边的全都压栈，如果栈不空，让curr为栈顶元素，优先从栈中弹出，最后curr = curr->right，这是为了满足inorder的需求，就是不能直接做curr->right，而是从curr->right->left开始做下一次循环。

调用的例子：

 ****** Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node

解法：

class BSTIterator {
public:
    stack<TreeNode* > S;
    TreeNode* curr;
    //@param root: The root of binary tree.
    BSTIterator(TreeNode *root) {
        // write your code here
        while (!S.empty() ) {
            S.pop();
        }
        curr = root;
    }

    //@return: True if there has next node, or false
    bool hasNext() {
        // write your code here
        return (curr != NULL || !S.empty() );
    }

    //@return: return next node
    TreeNode* next() {
        // write your code here
        while (curr != NULL) {
            S.push(curr);
            curr = curr->left;
        }
        curr = S.top();
        S.pop();
        TreeNode* next = curr;
        curr = curr->right;
        return next;
    }
};