NineRec

## question

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:
stack<TreeNode*> *stk;
BSTIterator(TreeNode *root) {
stk = new stack<TreeNode*>();
while (root) {
stk->push(root);
root = root->left;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !stk->empty();
}

/** @return the next smallest number */
int next() {
TreeNode* node = stk->top();
stk->pop();

int ret = node->val;

if (node->right) {
node = node->right;
while (node) {
stk->push(node);
node = node->left;
}
}
return ret;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
``````

### NineRec

Leetcode 173. Binary Search Tree Iterator

SnailTyan
2018/08/07
0
0
LeetCode 攻略 - 2019 年 6 月汇总

Create by jsliang on 2019-06-28 09:03:23 Recently revised in 2019-06-28 14:56:36 一 目录 不折腾的前端，和咸鱼有什么区别 目录 一 目录 二 前言 三 汇总  3.1 已攻略  3.2 Function ...

jsliang
06/28
0
0
LeetCode 分类刷题—— Stack

07/04
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自： https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

2018/09/04
0
0

nginx学习笔记

5
0
Spring Security 实战干货：玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战，如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证（Authentication），认证...

11
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie

12
0
PhotoShop 色调：RGB／CMYK 颜色模式

11
1

13
0