Sword finger offer II 055. Binary search tree iterator (medium binary search tree iterator)

The finger of the sword Offer II 055. Binary search tree iterator

Implement a binary search tree iterator class BSTIterator , Represents a binary search tree traversed in middle order （BST） The iterator ：

BSTIterator(TreeNode root) initialization BSTIterator An object of class .BST The root node root Will be given as part of the constructor . The pointer should be initialized to a value that does not exist in BST Number in , And the number is less than BST Any element in .
boolean hasNext() If there is a number traversing to the right of the pointer , Then return to true ; Otherwise return to false .
int next() Move the pointer to the right , Then return the number at the pointer .
Be careful , The pointer is initialized to a value that does not exist in BST Number in , So for next() The first call of will return BST The smallest element in .

It can be assumed next() The call is always valid , in other words , When calling next() when ,BST There is at least one next number in the middle order traversal of .

Example ：

Input
inputs = [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

explain
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

Tips ：

The number of nodes in the tree is in the range [1, 105] Inside
0 <= Node.val <= 106
Call at most 105 Time hasNext and next operation

Advanced ：

Can you design a solution that meets the following conditions ？next() and hasNext() The average time complexity of operation is O(1) , And use O(h) Memory . among h Is the height of the tree .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/kTOapQ
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

The subject itself is not difficult , Mainly consider how to achieve advanced conditions .
First of all, you can refer to 53 How to solve the problem ：https://blog.csdn.net/weixin_43942435/article/details/124079105
The next value of the current node can be found by iteration , But it is obviously inefficient to record the current node every time and then iterate from the root node , Then we consider saving the traversed nodes , The iterated nodes are saved by stack , Only iterate the effective path each time .

Answer key （Java）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class BSTIterator {
    
    private TreeNode root;
    private Deque<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
    
        this.root = root;
        stack = new LinkedList<>();
    }
    
    public int next() {
    
        while (root != null) {
    
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();// Take out the target node 
        int val = root.val;
        root = root.right;// Point to the next node （ Maybe not ）

        return val;
    }
    
    public boolean hasNext() {
    
        return root != null || !stack.isEmpty();
    }
}

/** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */