Binary Search Tree Iterator
2024-10-12 14:22:34
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.
采用中序遍历将节点压入栈中,由于要求存储空间为O(h),因此不能在一开始将所有节点全部压入,只是压入最左边一列。当取出一个节点时,压入其右子节点的所有左节点。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
stack <TreeNode*> stk;
int minres;
public:
BSTIterator(TreeNode *root) {
while(root)
{
stk.push(root);
root=root->left;
}
} /** @return whether we have a next smallest number */
bool hasNext() {
if(stk.empty())
return false;
TreeNode* top;
top=stk.top();
minres=top->val;
stk.pop();
TreeNode* cur=top->right;
if(cur)
{
stk.push(cur);
cur=cur->left;
while(cur)
{
stk.push(cur);
cur=cur->left;
}
}
return true;
} /** @return the next smallest number */
int next() {
return minres;
}
}; /**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
最新文章
- WSDL项目---处理消息
- reactjs
- Robot Framework--11 RF结合Jenkins
- (转)数据库获得当前时间getdate()
- asp.net Linq 实现分组查询
- [SAP] 外部系统调用SAP web service用户验证的简单方法
- 认识ExtJS(04)--常见Web框架的ExtJS改造
- Sematic库系列一
- FFT初解(转)
- python--对函数的理解
- Unity获取安卓手机运营商,电量,wifi信号强度,本地Toast,获取已安装apk,调用第三方应用,强制自动重启本应用
- rpm 相关问题
- 笔记:Hibernate DML
- linux 服务器网络有关的内核参数
- 001-为什么Java能这么流行
- appium 版本更新后的方法变化更新收集 ---持续更新
- Python 14 Html 基础
- redis make编译失败的原因
- NDK/JNI学习--环境搭建
- Go 实现异常处理机制