1586. Binary Search Tree Iterator II

 一刷 05/2022

Runtime: 87 ms, faster than 49.06% of Java online submissions for Binary Search Tree Iterator II.

Memory Usage: 71.9 MB, less than 92.60% of Java online submissions for Binary Search Tree Iterator II.

/**

 * 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 {

    // add a array to keep record of all elements that have been visited

    private Stack<TreeNode> stack;

    private List<Integer> visited;

    private int index;

    public BSTIterator(TreeNode root) {

        stack = new Stack<>();

        visited = new ArrayList<>();

        index = 0;

        while (root != null) {

            stack.push(root);

            root = root.left;

        }

    }

    

    public boolean hasNext() {

        return !stack.isEmpty() || index < visited.size();

    }

    

    public int next() {

        int val;

        if (index < visited.size()) {

            val = visited.get(index);

        } else {

            TreeNode curr = stack.pop();

            val = curr.val;

            visited.add(val);

            curr = curr.right;

            while (curr != null) {

                stack.push(curr);

                curr = curr.left;

            }

        }

        index++;

        return val;

    }

    

    public boolean hasPrev() {

        // index is pointing to the next value

        return index - 2 >= 0;

    }

    

    public int prev() {

        return visited.get(--index - 1);

    }

}

/**

 * Your BSTIterator object will be instantiated and called as such:

 * BSTIterator obj = new BSTIterator(root);

 * boolean param_1 = obj.hasNext();

 * int param_2 = obj.next();

 * boolean param_3 = obj.hasPrev();

 * int param_4 = obj.prev();

 */