Simple accepted Java code using stack and inorder traversal


  • -3
    L

    The idea is to use a stack: first push all elements into the stack by inorder traversal, then pop each element out as the next() method is called.

    public class BSTIterator {
    Stack<Integer> treeStack;

    public BSTIterator(TreeNode root) {
        treeStack = new Stack<Integer>();
        if (root!=null)
            eulerTraversal(root); //Push elements into stack
    }
    
    public void eulerTraversal(TreeNode v) {
        if (v.right!=null) {
            //Visit node v on the right
            eulerTraversal(v.right);
        }
        //Visit v
        treeStack.push(v.val);
        if (v.left!=null) {
            //Visit node v on the left
            eulerTraversal(v.left);
        }        
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !treeStack.isEmpty();
    }
    
    /** @return the next smallest number */
    public int next() {
        return treeStack.pop();
    }
    

    }


  • 0
    W

    O(h) memory?


Log in to reply
 

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