Using Queue combined with preorder thought instead of Stack.


  • 0
    Y
     Queue<TreeNode> queue;
    public BSTIterator(TreeNode root) {
         queue = new LinkedList<TreeNode>();
        pre(root);
    }
    public void pre(TreeNode root){
        if(root == null) return;
        pre(root.left);
        queue.add(root);
        pre(root.right);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !queue.isEmpty();
    }
    
    /** @return the next smallest number */
    public int next() {
        
       return queue.poll().val;
    }

  • 0
    U

    this is not preorder. it is in order. also u are using more memory which is not very good.


  • 0
    U
    This post is deleted!

Log in to reply
 

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