Java recursion solution


  • 0
    L

    Basically returns last index of current tree, and see if this is at last index.

    As in preorder, populated result is in form: T, L, R where T is root, L is left tree, R is right tree.

    Thus, recursion algo is:
    find(String[] a, index)

    1. if( a[index] == "#") return index
    2. if( a[index+1] != "#") return find( a, find(a,index+1)+1)
    3. return find(a,index+2)

    line 1, if index is #, this is the base case.
    line 2, if index+1 is number, then find(a,index+1) finds last index for L tree. Thus, keep finding the last index for R tree, therefore find( a, find(L) + 1 )
    line 3, find index for R tree, since L tree is #

    I believe the running time is O(n), correct me if i'm wrong

    Actual code:

    	public boolean isValidSerialization( String preorder )
    	{
    		if ( preorder.equalsIgnoreCase( "#" ) )
    			return true;
    		String[] c = preorder.split( "," );
    		if ( c.length < 3 )
    			return false;
    		System.out.println( find( c, 0 ) );
    		if ( find( c, 0 ) == c.length - 1 )
    			return true;
    		return false;
    	}
    
    	int find( String[] a, int index )
    	{
    		if ( index > a.length - 1 )
    			return a.length;
    		if ( a[index].equalsIgnoreCase( "#" ) )
    			return index;
    		if ( index + 1 > a.length - 1 )
    			return a.length;
    		if ( !a[index + 1].equalsIgnoreCase( "#" ) )
    			// find(a,index+1) finds last index of left tree
    			// find ( a, left tree + 1 ) = find ( a, right tree)
    			return find( a, find( a, index + 1 ) + 1 );
    		// find(a,index+2) finds last index of right tree, as left tree is #
    		return find( a, index + 2 );
    	}
    

Log in to reply
 

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