题解 | #重建二叉树#

typedef struct TreeNode BNode;

int find(int a[], int num, int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		if (a[i] == num)
			return i;
	}
	return -1;
}

BNode* Recon_Tree_Core(int* a_Pro, int* a_In, int length)
{
	BNode* p;
	int i;
	int Lenl, Lenr;
	p = (BNode*)malloc(sizeof(BNode));
	p->val = a_Pro[0];
	if (length == 1)
	{
		
		p->left = NULL;
		p->right = NULL;
		return p;
	}
	else
	{
		i=find(a_In, a_Pro[0],length);
		if (i == -1)
		{
			return NULL;
			printf("两序列可能不匹配");
		}
		Lenl = i;
		Lenr = length - i-1;
		if (Lenl >= 1)
			p->left = Recon_Tree_Core(a_Pro + 1, a_In, Lenl);
		else
			p->left = NULL;

		if (Lenr >= 1)
			p->right = Recon_Tree_Core(a_Pro+Lenl+1, a_In + Lenl + 1, Lenr);
		else
			p->right = NULL;

		return p;
	}
}

void Recon_Tree(BNode **root2,int* a_Pro,int* a_In,int length)
{
	if (length<=0)
	{
		printf("长度出错\n");
		return;
	}

	*root2=Recon_Tree_Core(a_Pro,a_In,length);
}



struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
    BNode *root;
    if(preLen>0)
        Recon_Tree(&root,pre,vin,preLen);
    else
        root=NULL;
    return root;
    
}