Binary Search Tree 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.

http://www.lintcode.com/en/problem/binary-search-tree-iterator/#

Discussion

Calling next() will return the next smallest number in the BST. 也就是返回中序遍历的第一个值，然后更新当前结点。

Solution

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

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

    //@return: return next node
    TreeNode* next() {
        // write your code here
        while(cur != NULL) {
            nodestk.push(cur);
            cur = cur->left;
        }
        TreeNode *tmp = nodestk.top();
        nodestk.pop();
        cur = tmp->right;
        return tmp;
    }
private:
    stack<TreeNode*> nodestk;
    TreeNode *cur;
};