My java code faster than 94.25% of java submissions


  • 0

    There are two places to find the successor of current node.
    1, the leftmost node in its right subtree.
    2, its lowest ancestor whose left child is also an ancestor

     public class BSTIterator {
        private TreeNode next;
        private TreeNode root;
    
       public BSTIterator(TreeNode root) {
            this.root = new TreeNode(Integer.MIN_VALUE);
            this.root.right = root;
            this.next = this.root;
        }
    
    public boolean hasNext() {
        if(next ==null) return false;
        if(next.right!=null){
            next = next.right;
            while(next.left!=null){
                next = next.left;
            }
            return true;
        }else{
            TreeNode temp = null;
            TreeNode cur = root;
            while(cur!= next){
                if(cur.val< next.val){
                    cur = cur.right;
                }else{
                    temp = cur;
                    cur=cur.left;
                }
            }
            next = temp;
            if(next!=null)
            return true;
            else return false;
        }
    }
    
                                        
    public int next() {
        return next.val;
    }
    

    }


  • 0

    This is terribly broken: 1) it crashes on the simple tree [1,0,1]; 2) it doesn't have average O(1) time for hasNext(); 3) it doesn't allow to call hasNext() multiple times before calling next(); 4) it doesn't allow to call next() without calling hasNext() before that (which would make perfect sense if someone knows beforehand that there is at least one node ahead).


  • 0
    This post is deleted!

  • 0

    Thanks for your advice. I will think about it :)
    Except for the first one: [1,0,1] is not a binary search tree.


  • 0

    Oh, I thought duplicates are allowed as long as the L <= R relationship is preserved. But looks like you're right.


Log in to reply
 

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