Shulou(Shulou.com)06/01 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.