This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the 173. Binary search tree iterator on LeetCode, of medium difficulty.

Tag: “Tree search”, “middle order traversal”

Implement a binary search tree iterator class BSTIterator, representing an iterator that traverses a binary search tree (BST) in middle order:

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root node of BST, root, is given as part of the constructor. Pointer should be initialized to a number that does not exist in BST and is smaller than any element in BST.
  • Boolean hasNext() returns true if a number exists when traversing to the right of the pointer; Otherwise return false.
  • Int next() moves the pointer to the right and returns the number at the pointer.

Note that the pointer is initialized to a number that does not exist in the BST, so the first call to next() returns the smallest element in the BST.

You can assume that the next() call is always valid, that is, when next() is called, there is at least one next number in the middle-order traversal of the BST.

Example:

Input [BSTIterator ", "" next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, 9, null, null, 20]], [], [], [], [], [], [], [], [], [[]] output null, 3, 7, 9, true, true, 15, true, 20. False] 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 (); / / returns FalseCopy the code

Tip:

  • The number of nodes in the tree is in the range [1, 10510^5105]
  • 0 <= Node.val <=
    1 0 6 10^6
  • Up to 10510^5105 hasNext and next operations are invoked

Advanced:

  • Can you design a solution that meets the following criteria? The next() and hasNext() operations have O(1)O(1)O(1) O(1) and use O(h)O(h)O(h) O(h) memory. Where h is the height of the tree.

The basic idea

The iterated version of the middle order traversal code is equivalent to split.

As we know, the basic logic of middle-order traversal is: process the left subtree -> process the current node -> process the right subtree.

The iterative approach is to use “stack” for processing:

  1. All left subtrees of the current node are pushed until no more are left
  2. Pop the last node pushed in (top element on the stack) and add the answer
  3. Repeat Step 1 to set the current pop-up node as the current node

Middle order traversal of binary trees

Iterative code for sequential traversal:

class Solution {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> d = new ArrayDeque<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        while(root ! =null| |! d.isEmpty()) {/ / step 1
            while(root ! =null) {
                d.addLast(root);
                root = root.left;
            }

            / / step 2
            root = d.pollLast();
            ans.add(root.val);

            / / step 3
            root = root.right;
        }
        returnans; }}Copy the code

In general, this is an iterative process: Step 1 -> Step 2 -> Step 3 -> Step 1…

“Equivalent Splitting” of middle-order Traversal Code

First, because in the next() method we need to print a value that executes “step 2” logic, and we need to add “step 1” and “step 3” before and after it.

Also, we have a hasNext() to deal with, and obviously hasNext() should correspond to whether or not our stack is empty.

To do this, we need to ensure that “Step 1” is executed in a timely manner after each output.

To sum up, we should go through “Step 1” once during initialization, and then “Step 2”, “Step 3”, and “Step 1” in the next() method.

Code:

class BSTIterator {
    Deque<TreeNode> d = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        / / step 1
        dfsLeft(root);
    }
    
    public int next(a) {
        / / step 2
        TreeNode root = d.pollLast();
        int ans = root.val;
        / / step 3
        root = root.right;
        / / step 1
        dfsLeft(root);
        return ans;
    }

    void dfsLeft(TreeNode root) {
        while(root ! =null) { d.addLast(root); root = root.left; }}public boolean hasNext(a) {
        return !d.isEmpty();
    }
}
Copy the code
  • Time complexity: Since each element is strictly “pushed” and “pushed” once, the complexity is amortized O(1)O(1)O(1)
  • Space complexity: the maximum number of nodes in the stack with the same depth is O(h)O(h)O(h)

The advanced

In fact, we can do O(1)O(1)O(1) O(1). How do we do that?

The last

This is No.173 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.