Java with Morris method, 4ms , 99%,without stack


  • 5

    Morris method is general used to travel Binary tree, and BST Iterator is just like travel tree.

    /** Morris */
    public class BSTIterator {
        private TreeNode read = null;
        public BSTIterator(TreeNode root) {
        read = root;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return read != null;
    }
    
    /** @return the next smallest number */
    public int next() {
        int x = 0;
        while ( read != null ){
            if ( read.left == null ){
                x = read.val;
                read = read.right;
                break;
            }else{
                TreeNode tempNode = read.left;
                // Find most 'right' child in left subtree
                while ( tempNode.right != null && tempNode.right != read ){
                    tempNode = tempNode.right;
                }
                if ( tempNode.right == null ){
                    tempNode.right = read;
                    read = read.left;
                }else{
                    x = tempNode.right.val;
                    tempNode.right = null;
                    read = read.right;
                    break;
                }
            }
        }// end_while
        return x;
    }// end_method
    

    }// end_class


  • 0
    Z
    This post is deleted!

  • 1

    @zhidu I don't find it obvious, can you explain a bit?

    @wantrd You only get to x = tempNode.right.val; when tempNode.right is read, so you can do x = read.val; instead.


  • 0

    @StefanPochmann said in Java with Morris method, 4ms , 99%,without stack:

    @zhidu I don't find it obvious, can you explain a bit?

    @wantrd You only get to x = tempNode.right.val; when tempNode.right is read, so you can do x = read.val; instead.

    yes, that would be better. thks : )


Log in to reply
 

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