Very concise solution by using stack in java


  • 19
    C
    public class BSTIterator {
        Stack<TreeNode> stack;
        public BSTIterator(TreeNode root) {
            stack = new Stack<TreeNode>();
            setNext(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            if(stack.isEmpty()) return -1;
            TreeNode node = stack.pop();
            int val = node.val;
            setNext(node.right);
            return val;
        }
        
        private void setNext(TreeNode root){
           while(root != null){
               stack.push(root);
               root = root.left;
           }
        }
    }

  • 0
    W

    It helps a lot!


  • 5
    A

    Just me nitpicking, you don't need this check:
    if(stack.isEmpty()) return -1;

    The problem didn't specify what to do on null input. -1 could potentially be a valid value in the TreeNode.


  • 0
    M

    in your solution next() is O(1) ?


  • 0
    A

    worst case O(n), average case O(1).


  • 0
    B

    Bravo !!!!
    It is really cool. I've wasted half an hour on this, haven't even thought about using the stack.
    Only notice that I should have something to store the node which has been passed without being visited. And I used a LinkedList rather than a stack.
    And my solution is more like iterative way rather than recursive.

    But I really like your idea.


  • 0
    C

    @chen2 said in Very concise solution by using stack in java:

    int val = node.val;

    well, actually you don't need this local variable val


Log in to reply
 

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