Leetcode problem solving -- 173 Binary search tree iterator

Iterative thinking

private TreeNode node;
private Stack<TreeNode> stack;

public BSTIterator(TreeNode root) {
    
    this.node =root;
    stack = new Stack<>();
}

public int next() {
    
    while (node !=null){
    
        stack.push(node);
        node = node.left;
    }
    node = stack.pop();
    int next = node.val;
    node = node.right;
    return next;
}

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

Ideas ： The iterative scheme based on the middle order traversal is improved
Every call next Get the value of a node
At the same time, the judgment conditions of the original cycle are extracted to hasNext Method to go

Be careful ：
This scheme is based on the understanding of the iterative method of middle order traversal , If a little partner doesn't know , And I want to know more about the explanation idea of middle order traversal iteration , Sure Click here to jump

Other options

In fact, you can recursively traverse the tree once , Put it in an array , Creating index variables can also achieve the above functions ,leetcode The official also has corresponding solutions , But I want to , In fact, iterators are originally what I can do as much as you want , If it is realized in this way , Small amount of data is OK , If it's big data , It will undoubtedly cause bad time loss , So I didn't write it out , Interested students can Click here Jump leetcode Official explanation