173. Binary Search Tree Iterator

本题考的是使用stack去非递归的中序遍历二叉搜索树

/**
 * 本题考的是使用stack去非递归的中序遍历二叉搜索树
 *
 */
class BSTIterator {
    
    //Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    stack<TreeNode*>s;
    TreeNode* current = NULL;
    
public:
    BSTIterator(TreeNode *root) {
        current = root;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return current != NULL || !s.empty();
    }
    
    /** @return the next smallest number */
    int next() {
        while (current) {
            s.push(current);
            current = current->left;
        }
        
        current = s.top();
        s.pop();
        int val = current->val;
        current = current->right;
        
        return val;
    }
};