Java recursion solution

• 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 );
}
``````

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