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.

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

Thanks to ，无需预先进行全部遍历。

利用中序遍历的递归思想：当子树的根节点访问完成后，后续节点为中序遍历该根节点右子树

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 class BSTIterator {11 public:12     stack
     
       st;13     14     BSTIterator(TreeNode *root) {15         pushLeft(root);16     }17 18     /** @return whether we have a next smallest number */19     bool hasNext() {20         return !st.empty();21     }22 23     /** @return the next smallest number */24     int next() {25         TreeNode *top = st.top();26         st.pop();27         pushLeft(top->right);28         return top->val;29     }30     31     void pushLeft(TreeNode *root) {32         if (root != NULL) {33             TreeNode *p = root;34             st.push(p);35             while (p->left) {36                 st.push(p->left);37                 p = p->left;38             }39         }40     }41 };42 43 /**44  * Your BSTIterator will be called like this:45  * BSTIterator i = BSTIterator(root);46  * while (i.hasNext()) cout << i.next();47  */