173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

Solution:
Take a while to figure out what this question is for... (Originally thought it is for the "second" smallest element in the Tree...) OK, here it is. It will always find the next smallest element in the BST if it exists. So if it is called from the beginning until the end, the sequence output will be the elements sorted from mid-order traversal (left -> root -> right) of BST.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *r = root;
        while(r){
            s.push(r);
            r = r->left;
        }
    }

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

    /** @return the next smallest number */
    int next() {
        TreeNode *t = s.top();
        int res = t->val;
        s.pop();
        if(t->right){
            t = t->right;
            while(t){
                s.push(t);
                t = t->left;
            }
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

http://www.cnblogs.com/grandyang/p/4231455.html