Leetcode brush question diary sword finger offer II 055. binary search tree iterator

Original link （https://leetcode.cn/problems/kTOapQ/）

Title Description

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

Ideas

For this tree, you can use a stack to store the values obtained after the first sequence traversal , The value required each time is the value at the top of the stack , When the stack has no value and no value is taken out before the top of the stack , Then it means that there is no number to traverse on the right side of the pointer . For traversal , There is no need to store it all at once , Can maintain this stack , Iterate to the left subtree every time you get the value , Then remove the final value , Then point the pointer of the node to the right subtree , Next time, just keep looking for the left subtree .

Code

/** * 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 {
    
	TreeNode curr;
	Stack<TreeNode> stack;
	public BSTIterator(TreeNode root) {
    
		curr=root;
		stack=new Stack<>();
		
    }
    
    public int next() {
    
    	while(curr!=null) {
    
    		stack.add(curr);
    		curr=curr.left;
    	}
    	curr=stack.pop();
    	int ans=curr.val;
    	curr=curr.right;
		return ans;

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

    }
}