173 Binary Search Tree Iterator

Leetcode

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.

boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.

int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"][[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
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

---

方法一：

直接做成队列，空间复杂度 o(n)

class BSTIterator {
    
    Queue<Integer> queue;

    public BSTIterator(TreeNode root) {
        queue = new LinkedList<>();
        inOrder(root);
    }
    
    private void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        queue.add(root.val);
        inOrder(root.right);
    }
    
    public int next() {
        return queue.poll();
    }
    
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

方法二：

使用一个栈，把所有左子树压入栈。弹出的时候，如果右子树不为空，则把右子树及其所有左子树，和左子树的左子树，和左子树的左子树的左子树等等，都要入栈。如果右子树为空，则要返回到上一个节点，如果当前节点是上一个节点的右子树，则不断返回。空间复杂度最差为 o(n) ，平均 o(log n)。

按理说方法一应该更快，但更费空间，但实际上 leetcode 测试的结果是相反的。

class BSTIterator {
    
    Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack=new LinkedList<>();
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
    }
    
    public int next() {
        TreeNode cur=stack.peek();
        int val=cur.val;
        if(cur.right!=null){
            TreeNode right=cur.right;
            stack.pop();
            while(right!=null){
                stack.push(right);
                right=right.left;
            }
        } else {
            stack.pop();
            TreeNode t=stack.peek();
            while(t!=null && t.right==cur){
                stack.pop();
                t=stack.peek();
            }
        }
        return val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}