leetcode@ [173] Binary Search Tree Iterator (InOrder traversal)
2024-08-25 06:00:31
https://leetcode.com/problems/binary-search-tree-iterator/
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.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public: queue<int> Q;
public:
BSTIterator(TreeNode *root) {
inOrder(root, Q);
} void inOrder(TreeNode* root, queue<int>& Q) {
if(root != NULL) {
inOrder(root->left, Q);
Q.push(root->val);
inOrder(root->right, Q);
}
} /** @return whether we have a next smallest number */
bool hasNext() {
return !Q.empty();
} /** @return the next smallest number */
int next() {
int next_min = Q.front();
Q.pop();
return next_min;
}
}; /**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
最新文章
- Bootstrap<;基础三>; 排版
- [非原创]Project facet Java version 1.8 is not supported解决记录
- 多线程下的 Lambda表达式 异步 WebClient 读取程序图标,来作为托盘 图标 logo ico
- 作业2源程序版本管理软件优缺点,及Github注册
- Mybatis之Oracle增删查改示例--转
- Make My GitHub Pages
- Tkinter教程之Grid篇
- MEF 编程指南(七):使用目录
- BNUOJ-26580 Software Bugs KMP匹配,维护
- [Protractor] Running tests on multiple browsers
- 两年前实习时的文档——MMC学习总结
- (一)html之基本结构
- 11g init DB software and database
- 前言《iOS网络高级编程:iPhone和iPad的企业应用开发》(书籍学习)
- 【转】完美解决Python与anaconda之间的冲突问题
- Docker在Linux上运行NetCore系列(二)把本地编译好的镜像发布到线上阿里云仓库
- Jmeter接口自动化
- Amundsen — Lyft’s data discovery &; metadata engine
- ACG图片站\python爬虫\LAMP环境
- Install Virtualbox on ubuntu
热门文章
- 手机开发类型jquery的框架Zepto(API)
- CSS+DIV布局初练—DIV元素必须成对出现?
- border-radius的水平和竖直半径
- eclipse如何导入PHP的项目
- C#.Net 如何动态加载与卸载程序集(.dll或者.exe)4-----Net下的AppDomain编程 [摘录]
- 键盘KeyCode值列表
- WINCE6.0+IMX515通过cfimager.exe烧录镜像文件
- tcp连接的3次握手
- bzoj1015:1015: [JSOI2008]星球大战starwar
- 【spring-boot】快速构建spring-boot微框架