What is the binary search tree iterator?
This article introduces what the binary search tree iterator refers to, the content is very detailed, interested friends can refer to, hope to be helpful to you.
Implement a binary search tree iterator. You will initialize the iterator with the root node of the binary search tree.
Calling next () returns the next smallest number in the binary search tree.
Example:
BSTIterator iterator = new BSTIterator (root); iterator.next ()
/ / return 3 iterator.next ()
/ / return 7 iterator.hasNext ()
/ / return true iterator.next ()
/ / return 9 iterator.hasNext ()
/ / return true iterator.next ()
/ / return 15 iterator.hasNext ()
/ / return true iterator.next ()
/ / return 20 iterator.hasNext ()
/ / return false
Answer:
1class BSTIterator {
two
3 private Stack stack = new Stack ()
four
5 public BSTIterator (TreeNode root) {
6 pushAll (root)
7}
eight
9 public boolean hasNext () {
10 return! stack.isEmpty ()
11}
twelve
13 public int next () {
14 TreeNode tmpNode = stack.pop ()
15 pushAll (tmpNode.right)
16 return tmpNode.val
17}
eighteen
19 private void pushAll (TreeNode node) {
20 for (; node! = null; stack.push (node), node = node.left)
21}
22}
Parsing:
If you are familiar with the dfs (depth first search) of binary trees, this question is easy to understand.
On the binary search tree iterator refers to what is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.
