Nuggets team number online, help you Offer impromptu! Click for details

Implement a binary search tree iterator class BSTIterator, representing an iterator that traverses the binary search tree (BST) in middle order: BSTIterator(TreeNode root) initializes an object of 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 = 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 False

Their thinking

When the node currently traversed is out of the stack, the right node and all the children on the right node are pushed onto the stack to realize the traversal

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 {

        Stack<TreeNode> stack=new Stack<>();
        public BSTIterator(TreeNode root) {
            while(root! =null) { stack.add(root); root=root.left; }}public int next(a) {

            TreeNode pop = stack.pop();
            TreeNode right = pop.right;
            while(right! =null)
            {
                stack.add(right);
                right=right.left;
            }
            return pop.val;
        }

        public boolean hasNext(a) {

           return !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(); * /
Copy the code