Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Callingnext()will return the next smallest number in the BST.
Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.
即找出二叉查找树中最小的元素。
思路：找最小值，可以参考中序遍历，借助栈！每弹出一个元素，，才增加栈中元素，不用马上遍历整颗树!
实现代码：
class BSTIterator {stack<TreeNode *> myStack;public:BSTIterator(TreeNode *root) {TreeNode *node=root;while(node!=NULL){myStack.push(node);node = node->left;}}/** @return whether we have a next smallest number */bool hasNext() {return !myStack.empty();}/** @return the next smallest number */int next() {TreeNode *tmpNode = myStack.top();int res = tmpNode->val;myStack.pop();tmpNode=tmpNode->right;while(tmpNode!=NULL){myStack.push(tmpNode);tmpNode = tmpNode->left;}return res;}};
愚者用肉体监视心灵，智者用心灵监视肉体
