Reconstruct a binary tree given two sequences of node traversals, one from inorder and one from postorder traversal.

Question

Jaime · Accepted Answer

void buildTree(Node r,int []inorder,int low,int hi, int item)
    {
        if(low > hi)
            return;
        int k = findRoot(item,inorder,low,hi);
        if(k >= 0)
        {
            r = new Node();
            r.item = item;
        }
        int leftson = postq.poll();
        buildTree(r.left,inorder,low,k-1,leftson);
        int rightson = postq.poll();
        buildTree(r.right,inorder,k+1,hi,rightson);
    }

Alina · Answer

sub recon {
	my ( $in, $post ) = @_;
	return undef unless @$in;
	if ( @$in == 1 ) {
		return +{
			value => $in->[0],
		};
	}
	my $root = pop @$post;
	my $bst = +{
		value => $root
	};
	for ( my $i = 0; $i [$i] == $root;
		$bst->{left} = recon( [ ( @$in )[0..$i-1] ], [ ( @$post )[0..$i-1] ] );
		$bst->{right} = recon( [ ( @$in )[$i+1..@$in-1] ], [ ( @$post )[$i..@$post-1] ] );
	}
	return $bst;
}

Yelp

Yelp Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches