given in-order and pre-order, re-construct a tree

Here is my code :

 

//    In-order traversal : c b f d g a e  (Left, Root, Right)
//     Pre-order traversal : a b c d f g e. (Root, left, right)
//
//
    static int rootIdx = 0;
    public Node reConstruct( char[] inorder, char[] preorder, int start, int end )
    {
        if( rootIdx == preorder.length -1 )
        {
            return new Node ( postOrder[rootIdx] );
        }
        if( start == end )
        {
            reutrn new Node( inorder[start] );
        }
        char rootValue = postOrder[rootIdx++];
        Node root = new Node( rootValue );
        int rootPos = findRoot( inorder,  rootValue, start, end );

        root.left = reconstruct( inorder, preorder, 0, rootPos-1 );
        root.right = reconstruct( inorder, preorder, rootPos + 1, end );
        return root;
    }

    int findRoot( char[] inorder, char rootValue, int start, int end )
    {
        for( int i = start; i <= end; i++ )
        {
            if( inorder[i] == rootValue )
            {
                return i;
            }
        }
    }

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s