binary-search-tree-iterator

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Implement the <code>BSTIterator</code> class that represents an iterator over the <a href="https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)" target="_blank">in-order traversal</a> of a binary search tree (BST):

<ul>
	<li><code>BSTIterator(TreeNode root)</code> Initializes an object of the <code>BSTIterator</code> class. The <code>root</code> of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.</li>
	<li><code>boolean hasNext()</code> Returns <code>true</code> if there exists a number in the traversal to the right of the pointer, otherwise returns <code>false</code>.</li>
	<li><code>int next()</code> Moves the pointer to the right, then returns the number at the pointer.</li>
</ul>

Notice that by initializing the pointer to a non-existent smallest number, the first call to <code>next()</code> will return the smallest element in the BST.

You may assume that <code>next()</code> calls will always be valid. That is, there will be at least a next number in the in-order traversal when <code>next()</code> is called.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png" style="width: 189px; height: 178px;" />
<pre>
Input
[&quot;BSTIterator&quot;, &quot;next&quot;, &quot;next&quot;, &quot;hasNext&quot;, &quot;next&quot;, &quot;hasNext&quot;, &quot;next&quot;, &quot;hasNext&quot;, &quot;next&quot;, &quot;hasNext&quot;]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 105]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 106</code></li>
	<li>At most <code>105</code> calls will be made to <code>hasNext</code>, and <code>next</code>.</li>
</ul>

&nbsp;
Follow up:

<ul>
	<li>Could you implement <code>next()</code> and <code>hasNext()</code> to run in average <code>O(1)</code> time and use&nbsp;<code>O(h)</code> memory, where <code>h</code> is the height of the tree?</li>
</ul>

Binary Search Tree Iterator

Binary Tree Inorder Traversal

binary-tree-inorder-traversal

二叉树的中序遍历

Flatten 2D Vector

flatten-2d-vector

展开二维向量

Zigzag Iterator

zigzag-iterator

锯齿迭代器

Peeking Iterator

peeking-iterator

窥视迭代器

Inorder Successor in BST

inorder-successor-in-bst

二叉搜索树中的中序后继

Binary Search Tree Iterator II

binary-search-tree-iterator-ii

二叉搜索树迭代器 II

Stack

Tree

Design

Binary Search Tree

Binary Tree

Iterator

&#23454;&#29616;&#19968;&#20010;&#20108;&#21449;&#25628;&#32034;&#26641;&#36845;&#20195;&#22120;&#31867;<code>BSTIterator</code> &#65292;&#34920;&#31034;&#19968;&#20010;&#25353;&#20013;&#24207;&#36941;&#21382;&#20108;&#21449;&#25628;&#32034;&#26641;&#65288;BST&#65289;&#30340;&#36845;&#20195;&#22120;&#65306;
<div class="original__bRMd">
<div>
<ul>
	<li><code>BSTIterator(TreeNode root)</code> &#21021;&#22987;&#21270; <code>BSTIterator</code> &#31867;&#30340;&#19968;&#20010;&#23545;&#35937;&#12290;BST &#30340;&#26681;&#33410;&#28857; <code>root</code> &#20250;&#20316;&#20026;&#26500;&#36896;&#20989;&#25968;&#30340;&#19968;&#37096;&#20998;&#32473;&#20986;&#12290;&#25351;&#38024;&#24212;&#21021;&#22987;&#21270;&#20026;&#19968;&#20010;&#19981;&#23384;&#22312;&#20110; BST &#20013;&#30340;&#25968;&#23383;&#65292;&#19988;&#35813;&#25968;&#23383;&#23567;&#20110; BST &#20013;&#30340;&#20219;&#20309;&#20803;&#32032;&#12290;</li>
	<li><code>boolean hasNext()</code> &#22914;&#26524;&#21521;&#25351;&#38024;&#21491;&#20391;&#36941;&#21382;&#23384;&#22312;&#25968;&#23383;&#65292;&#21017;&#36820;&#22238; <code>true</code> &#65307;&#21542;&#21017;&#36820;&#22238; <code>false</code> &#12290;</li>
	<li><code>int next()</code>&#23558;&#25351;&#38024;&#21521;&#21491;&#31227;&#21160;&#65292;&#28982;&#21518;&#36820;&#22238;&#25351;&#38024;&#22788;&#30340;&#25968;&#23383;&#12290;</li>
</ul>

&#27880;&#24847;&#65292;&#25351;&#38024;&#21021;&#22987;&#21270;&#20026;&#19968;&#20010;&#19981;&#23384;&#22312;&#20110; BST &#20013;&#30340;&#25968;&#23383;&#65292;&#25152;&#20197;&#23545; <code>next()</code> &#30340;&#39318;&#27425;&#35843;&#29992;&#23558;&#36820;&#22238; BST &#20013;&#30340;&#26368;&#23567;&#20803;&#32032;&#12290;
</div>
</div>

&#20320;&#21487;&#20197;&#20551;&#35774;&nbsp;<code>next()</code>&nbsp;&#35843;&#29992;&#24635;&#26159;&#26377;&#25928;&#30340;&#65292;&#20063;&#23601;&#26159;&#35828;&#65292;&#24403;&#35843;&#29992; <code>next()</code>&nbsp;&#26102;&#65292;BST &#30340;&#20013;&#24207;&#36941;&#21382;&#20013;&#33267;&#23569;&#23384;&#22312;&#19968;&#20010;&#19979;&#19968;&#20010;&#25968;&#23383;&#12290;

&nbsp;

&#31034;&#20363;&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png" style="width: 189px; height: 178px;" />
<pre>
&#36755;&#20837;
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
&#36755;&#20986;
[null, 3, 7, true, 9, true, 15, true, 20, false]

&#35299;&#37322;
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // &#36820;&#22238; 3
bSTIterator.next(); // &#36820;&#22238; 7
bSTIterator.hasNext(); // &#36820;&#22238; True
bSTIterator.next(); // &#36820;&#22238; 9
bSTIterator.hasNext(); // &#36820;&#22238; True
bSTIterator.next(); // &#36820;&#22238; 15
bSTIterator.hasNext(); // &#36820;&#22238; True
bSTIterator.next(); // &#36820;&#22238; 20
bSTIterator.hasNext(); // &#36820;&#22238; False
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li>&#26641;&#20013;&#33410;&#28857;&#30340;&#25968;&#30446;&#22312;&#33539;&#22260; <code>[1, 105]</code> &#20869;</li>
	<li><code>0 <= Node.val <= 106</code></li>
	<li>&#26368;&#22810;&#35843;&#29992; <code>105</code> &#27425; <code>hasNext</code> &#21644; <code>next</code> &#25805;&#20316;</li>
</ul>

&nbsp;

&#36827;&#38454;&#65306;

<ul>
	<li>&#20320;&#21487;&#20197;&#35774;&#35745;&#19968;&#20010;&#28385;&#36275;&#19979;&#36848;&#26465;&#20214;&#30340;&#35299;&#20915;&#26041;&#26696;&#21527;&#65311;<code>next()</code> &#21644; <code>hasNext()</code> &#25805;&#20316;&#22343;&#25674;&#26102;&#38388;&#22797;&#26434;&#24230;&#20026; <code>O(1)</code> &#65292;&#24182;&#20351;&#29992; <code>O(h)</code> &#20869;&#23384;&#12290;&#20854;&#20013; <code>h</code> &#26159;&#26641;&#30340;&#39640;&#24230;&#12290;</li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support