173 Binary Search Tree Iterator

来源：Leetcode

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

题目：
Design an iterator over a binary search tree with the following properties: Elements are visited in ascending order (i.e. an inorder traversal) next() and hasNext() queries run in O(1) time in average.
Example
For the following binary search tree, inorder traversal by using iterator is [1, 6, 10, 11, 12]

          10

        /     \

     1          11

        \           \

           6           12


代码：

 /**  
  * 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) {  
     cur = root;  
   }  
   
   /** @return whether we have a next smallest number */  
   bool hasNext() {  
     return cur || !s.empty();    
   }  
   
   /** @return the next smallest number */  
   int next() {  
     while (cur || !s.empty()) {  
       if (cur) {  
         s.push(cur);  
         cur = cur->left;  
       } else if (!s.empty()) {  
         TreeNode* n = s.top();   
         s.pop();  
         cur = n->right;  
         return n->val;  
       }  
     }  
   }  
     
 private:  
   TreeNode* cur;  
   stack<TreeNode*> s;  
 };