程式設計之美3.9---重建二叉樹&&判斷結果是否能夠重建

#include<iostream>
using namespace std;

struct Node
{
	Node* pLeft;
	Node* pRight;
	int nValue;
};

bool isValid(int * pPreOrder,int *pInOrder,int nTreeLen)
{
	if(nTreeLen==0)
	{
		return true;
	}
	if(pPreOrder==NULL||pInOrder==NULL)
	{
		return true;
	}
	else
	{
		int LeftLen=0;
		int RightLen=0;
		int i=0;
		for(;i<nTreeLen;i++)
		{
			if(pInOrder[i]==pPreOrder[0])
				break;
		}
		if(i==nTreeLen)
		{
			return false;
		}
		else
		{
			LeftLen=i;
			RightLen=nTreeLen-i-1;
			bool ls=isValid(pPreOrder+1,pInOrder,LeftLen);
			bool rs=isValid(pPreOrder+1+LeftLen,pInOrder+1+LeftLen,RightLen);
			return ls&&rs;
		}
	}


}


void Rebuild(int * pPreOrder,int *pInOrder,int nTreeLen,Node ** pRoot)
{
	if(nTreeLen==0)
	{
		return;
	}
	if(pPreOrder==NULL||pInOrder==NULL)
	{
		return;
	}
	else
	{
		Node* temp=(Node *)malloc(sizeof(Node));
		temp->nValue=pPreOrder[0];
		temp->pLeft=NULL;
		temp->pRight=NULL;
		*pRoot=temp;
		int LeftLen=0;
		int RightLen=0;
		int i=0;
		for(;i<nTreeLen;i++)
		{
			if(pInOrder[i]==temp->nValue)
				break;
		}
		LeftLen=i;
		RightLen=nTreeLen-i-1;
		Rebuild(pPreOrder+1,pInOrder,LeftLen,&(temp->pLeft));
		Rebuild(pPreOrder+1+LeftLen,pInOrder+1+LeftLen,RightLen,&(temp->pRight));
	}
}

void ProPrint(Node* root)
{
	if(root==NULL)
		return;
	cout<<root->nValue<<endl;
	ProPrint(root->pLeft);
	ProPrint(root->pRight);
}

void MidPrint(Node* root)
{
	if(root==NULL)
		return;
	MidPrint(root->pLeft);
	cout<<root->nValue<<endl;
	MidPrint(root->pRight);
}

int main()
{
	int a[6]={1,2,4,3,5,6};
	int b[6]={4,2,1,5,3,6};
	if(isValid(a,b,6))
	{
		Node * prt;
		Rebuild(a,b,6,&prt);
		cout<<"前序周遊："<<endl;
		ProPrint(prt);
		cout<<"中序周遊："<<endl;
		MidPrint(prt);
	}
	else
		cout<<"Not Valid!"<<endl;

	
	int a0[6]={1,2,4,3,5,6};
	int b0[6]={7,2,1,5,3,6};
	if(isValid(a0,b0,6))
	{
		Node * prt;
		Rebuild(a0,b0,6,&prt);
		cout<<"前序周遊："<<endl;
		ProPrint(prt);
		cout<<"中序周遊："<<endl;
		MidPrint(prt);
	}
	else
		cout<<"Not Valid!"<<endl;


	int a1[1]={1};
	int b1[1]={1};
	if(isValid(a1,b1,1))
	{
		Node * prt;
		Rebuild(a1,b1,1,&prt);
		cout<<"前序周遊："<<endl;
		ProPrint(prt);
		cout<<"中序周遊："<<endl;
		MidPrint(prt);
	}
	else
		cout<<"Not Valid!"<<endl;

	int a2[6]={1,2,4,3,5,6};
	int b2[6]={3,2,1,5,6,4};
	if(isValid(a2,b2,6))
	{
		Node * prt;
		Rebuild(a2,b2,6,&prt);
		cout<<"前序周遊："<<endl;
		ProPrint(prt);
		cout<<"中序周遊："<<endl;
		MidPrint(prt);
	}
	else
		cout<<"Not Valid!"<<endl;



	return 0;
}