Accepted Java solution using stack.


  • 3
    P

    The idea is to use a stack to store ancestors of a left child.

    private TreeNode mCurrent;
    private Stack<TreeNode> mAncestors;
    
    public BSTIterator(TreeNode root) {
        this.mCurrent = root;
        this.mAncestors = new Stack<TreeNode>();
        while (mCurrent != null) {
        	mAncestors.push(mCurrent);
        	mCurrent = mCurrent.left;
        }
    }
    
    public boolean hasNext() {
        return (mCurrent != null && mCurrent.right != null) 
        		|| !mAncestors.isEmpty();
    }
    
    public int next() {
    	if (mCurrent == null) {
    		mCurrent = mAncestors.pop();
    	} else if (mCurrent.right != null) {
    		mCurrent = mCurrent.right;
    		while (mCurrent.left != null) {
            	mAncestors.push(mCurrent);
            	mCurrent = mCurrent.left;
            }
        } else {
        	mCurrent = mAncestors.pop();
        }
        return mCurrent.val;
    }

  • 1
    A

    // Thx for the post, the following is my version with a little revised in next()

    Stack<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        TreeNode curr = root;
        while(curr != null){
            stack.push(curr);
            curr = curr.left; 
        }
    }
    
    public boolean hasNext() {
        return !stack.empty(); 
    }
    
    public int next() {
        TreeNode curr = stack.pop();
        int rev = curr.val; 
        if(curr.right != null){
            curr = curr.right;
            stack.push(curr);
            curr = curr.left;
            while(curr != null){
                stack.push(curr);
                curr = curr.left;
            }
        }
        return rev; 
    }

  • 0
    G

    There is no need to store current element. You can get next element from the stack.


  • 0
    Y
    This post is deleted!

  • 0
    C

    I got the same idea at first, but is it O(1) or O(h) time?


  • 0
    A

    For the above solution, hasNext( ) is O(1), but next( ) is O(h) because before returning the popped value from the stack, we need to store all the next smallest elements onto the stack if they exist.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.