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.
相当于遍历二叉搜索树，借助栈即可实现：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 11 class BSTIterator {12 private:13 stack stk;14 TreeNode * node;15 public:16 BSTIterator(TreeNode *root) {17 node = root;18 }19 20 /** @return whether we have a next smallest number */21 bool hasNext() {22 return (node || !stk.empty());23 }24 25 /** @return the next smallest number */26 int next() {27 TreeNode * res = NULL;28 if(node == NULL){29 res = stk.top();30 stk.pop();31 node = res->right;32 }else{33 while(node->left != NULL){34 stk.push(node);35 node = node->left;36 }37 res = node;38 node = node->right;39 }40 return res->val;41 }42 };43 44 /**45 * Your BSTIterator will be called like this:46 * BSTIterator i = BSTIterator(root);47 * while (i.hasNext()) cout << i.next();48 */ 或者可以看看另一种做法，就是在构造迭代器的时候就将第一个最小的值准备好，不过二者的思路大体是一样的：
1 class BSTIterator { 2 private: 3 stack s; 4 public: 5 BSTIterator(TreeNode *root) { 6 while(root){ 7 s.push(root); 8 root == root->left; 9 }10 }11 12 /** @return whether we have a next smallest number */13 bool hasNext() {14 return !s.empty();15 }16 17 /** @return the next smallest number */18 int next() {19 TreeNode * n = s.top();20 ret = n.val;21 s.pop();22 n = n->right;23 while(n){24 s.push(n);25 n = n->left;26 }27 return res;28 }29 }; 或者就是直接的开始的时候就进行中序遍历，然后装入一个队列，需要的时候直接pop就可以了：
1 class BSTIterator { 2 public: 3 queue q; 4 map m; 5 stack s; 6 7 BSTIterator(TreeNode *root) { 8 if(root) 9 s.push(root);10 while(!s.empty()){11 TreeNode * t = s.top();12 if(t->left && m[t->left] == false){13 s.push(t->left);14 m[t->left] = true; //表示这条路已经报错过了，下次走的不经过这里15 continue;16 }17 q.push(t->val);18 s.pop();19 if(t->right && m[t->right] == false){20 s.push(t->right);21 m[t->right] = true;22 }23 }24 }25 26 /** @return whether we have a next smallest number */27 bool hasNext() {28 if(!q.empty())29 return true;30 return false;31 }32 33 /** @return the next smallest number */34 int next() {35 if(hasNext()){36 int t = q.front();37 q.pop();38 return t; 39 }40 }41 }; java版本的如下所示，首先是用一个Stack来实现的：
1 public class BSTIterator { 2 Stack s; 3 TreeNode n; 4 public BSTIterator(TreeNode root) { 5 s = new Stack (); 6 n = root; 7 } 8 9 /** @return whether we have a next smallest number */10 public boolean hasNext() {11 return n != null || !s.isEmpty();12 }13 14 /** @return the next smallest number */15 public int next() {16 TreeNode res = null;17 if(n == null){18 n = s.pop();19 res = n;20 n = n.right;21 }else{22 while(n.left != null){23 s.push(n);24 n = n.left;25 }26 res = n;27 n = n.right;28 }29 return res.val;30 }31 } 另一个的版本也如下所示，同样是将所有的数字再构造的时候就中序遍历完成，然后的hasNext以及next就非常简单了。
1 public class BSTIterator { 2 Queue queue; 3 Stack stack; 4 HashMap map; //表示这个Node是否已经在queue存在着了，0表示没有，1表示已经存在了 5 public BSTIterator(TreeNode root) { //对象构造的时候将所有的值就全部的装入了一个队列中 6 queue = new LinkedList (); 7 stack = new Stack (); 8 map = new HashMap (); 9 TreeNode node;10 if(root == null)11 return;12 stack.push(root);13 while(!stack.isEmpty()){14 node = stack.peek();15 while(node.left != null && !map.containsKey(node.left)){16 stack.push(node.left);17 map.put(node.left, 1);18 node = node.left;19 }20 queue.add(node.val);21 stack.pop();22 if(node.right != null && !map.containsKey(node.right)){23 stack.push(node.right);24 map.put(node.right, 1);25 }26 }27 }28 29 /** @return whether we have a next smallest number */30 public boolean hasNext() {31 return !queue.isEmpty();32 }33 34 /** @return the next smallest number */35 public int next() {36 return queue.poll();37 }38 }