1、题目描述
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.
Example:
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false
</pre>
Note:
-
next()andhasNext()should run in average O(1) time and uses O(h) memory, where h is the height of the tree. - You may assume that
next()call will always be valid, that is, there will be at least a next smallest number in the BST whennext()is called.
2、问题描述：
- 二叉树的非递归中序遍历。
3、问题关键：
- 1.用栈实现，先加根再加左子树。
- 2.弹出的时候，判断是否有右子树，如果有压入栈，在将右子树的左子树全压入。
4、C++代码：
class BSTIterator {
public:
stack<TreeNode*> stk;//建立一个栈。
BSTIterator(TreeNode* root) {
while(root){
stk.push(root);
root = root->left;//根左左左左左。。。。。
}
}
/** @return the next smallest number */
int next() {
auto t = stk.top();
stk.pop();//取出栈顶元素。
for (auto p = t->right; p; p = p->left)//将弹出结点的右子树加入，右左左左左左。。。。
stk.push(p);
return t->val;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !stk.empty();//判断栈是否为空。
}
};
