My 5ms JAVA code with explanation which beats 95%


  • 4
    G

    Basically, my code is trying to modify the structure of the right subtree to make sure the "next" node to be the right son of current "root", when each time we call function next().

    Let's consider a tree now. "root" is the current node of the tree.
    If hasnext()==true, then there are 2 scenarios.(Please draw the tree to better understand.)

    (1) Its right son doesn't have a left son. This scenario is easy and we can simply return the right son's val and meanwhile set root to the right son.

    (2) Its right son has left son. Let's use "next" to represent the right son. Then we should do "next = next.left" until it doesn't have a left son. Now the "next.val" is what we'd like to return.
    However, in this case how can we keep going?

    My idea is to modify the structure of the tree, in order to make the "next" node to be the right son of current "root", make the "next" node to be the right son of current "root", make the "next" node to be the right son of current "root"(Repeat important things for 3 times). Basically, there are two things to consider.

    Firstly, since we want to move node "next", don't forget about the right subtree of it!!! So we need a node called "parent" to store the original parent of node "next" and then we can set parent.left = next.right.

    Secondly, we need to have a TreeNode called "right" to store the original right son of root. Then we can set root.right = next and next.right = right.

    Then we get a new right subtree and we just set root = next before we return next.val.

    public class BSTIterator {
    TreeNode root = new TreeNode(0); 
    public BSTIterator(TreeNode root) {
        this.root.right = root;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return (root.right!=null);
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode next = root.right;
        if (next.left==null) {
        	root = next;
        	return next.val; 
        }
        TreeNode right = root.right;
        TreeNode parent = root;
        while (next.left!=null) {
        	parent = next;
        	next = next.left;
        }
        parent.left = next.right;
        root.right = next;
        next.right = right;
        root = next;
        return next.val;
    }
    

    }


Log in to reply
 

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