173. 二叉搜索树迭代器
2023-02-18 16:34:57 时间
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
class BSTIterator {
private:
vector<TreeNode*> S;
public:
BSTIterator(TreeNode* root){
while(root){
S.push_back(root);
root = root->left;
}
}
int next() {
TreeNode* t = S.back();
S.pop_back();
int val = t->val;
t = t->right;
while(t){
S.push_back(t);
t = t->left;
}
return val;
}
bool hasNext() {
return !S.empty();
}
};
测试代码:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct TreeNode {
char data;
TreeNode *left;
TreeNode *right;
};
typedef TreeNode* BTree;
class BSTIterator {
private:
vector<TreeNode*> S;
TreeNode* root;
public:
void init(){
root=CreateBTree();
TreeNode* troot=root;
while(troot){
S.push_back(troot);
troot = troot->left;
}
}
char next() {
TreeNode* t = S.back();
S.pop_back();
char val = t->data;
t = t->right;
while(t){
S.push_back(t);
t = t->left;
}
return val;
}
bool hasNext() {
return !S.empty();
}
BTree CreateBTree()
{
BTree bt = NULL;
char ch;
cin>>ch;
if (ch != '#')
{
bt = new TreeNode;
bt->data = ch;
bt->left = CreateBTree();
bt->right = CreateBTree();
}
return bt;
}
//层序遍历
void LevelOrder(){
queue<TreeNode*>q;
TreeNode *front;
if(root==NULL)return;
q.push(root);
while (!q.empty())
{
front = q.front();
q.pop();
if (front->left)
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
cout<<front->data;
}
}
};
int main(){
BSTIterator iterator;
iterator.init();
iterator.LevelOrder();
cout<<endl;
cout<<iterator.next()<<endl;
cout<<iterator.hasNext()<<endl;
cout<<iterator.next()<<endl;
cout<<iterator.hasNext()<<endl;
cout<<iterator.next()<<endl;
cout<<iterator.hasNext()<<endl;
}
12##3##
相关文章
- 可怕!CPU暗藏了这些未公开的指令!
- 一个故事看懂CPU的SIMD技术
- CPU被挖矿,Redis竟是内鬼!
- 一次fork引发的惨案!
- 一个故事看懂CPU的TLB
- 现代操作系统管理内存,到底是分段还是分页,段寄存器还有用吗?
- 一个故事看懂HTTPS
- 一个故事看懂进程间通信技术
- 一个故事看懂机械硬盘原理
- 一个故事看懂内存条工作原理
- CPU:网卡老哥,你到底怎么工作的?
- 主板上来了一个新邻居,CPU慌了!
- 还不懂Docker?一个故事安排的明明白白!
- 五分钟看懂抓包神技:DPDK
- 假如把Redis服务器们拉到一个群,看看他们是怎么工作的?
- 从创建进程到进入main函数,发生了什么?
- 一口气看完45个寄存器,CPU核心技术大揭秘
- 协程到底是什么?看完这个故事明明白白!
- 一个故事看懂AI神经网络工作原理
- 一个爬虫的故事:这是人干的事儿?