pta7_11玩转二叉树（先序中序建树）

makeTree(先序，中序，长度){
    if 长度==0 return 空
    else 新建节点
    for 找到pre[0]=mid[i]
    tree[当前].left=makeTree(左子树);
    tree[当前].righr=makeTree(右子树);
    return 当前;
}

struct Node{     int date;     int left,right;
};
Node tree[50];
int cnt=0;
int makeTree(int pre[],int mid[],int len){
	if(len==0) return -1;
	int id=cnt++;
	tree[id].date=pre[0];
	int i;
	for(i=0;mid[i]!=pre[0];i++) ;
	tree[id].left=makeTree(pre+1,mid,i);
	tree[id].right=makeTree(pre+i+1,mid+i+1,len-i-1);
	return id;
}
//tree[0]是根节点

int cnt=0;
int makeTree(int la,int ra,int lb,int rb){//中序左，右，先序左，右
	if(la>ra) return -1;
	int id=cnt++;
	tree[id].date=pre[lb];
	int i; for(i=la;pre[lb]!=mid[i];i++) ;
	int len=i-la;//左子树长度 
	tree[id].left=makeTree(la,i-1,lb+1,lb+len);
	tree[id].right=makeTree(i+1,ra,lb+1+len,rb);
	return id;
}

#include <bits/stdc++.h>
using namespace std;

struct Node{
	int date;
	int left,right;
};
Node tree[50];

int  n;
int pre[50],mid[50];

int cnt=-1;
int makeTree(int pre[],int mid[],int len){
	if(len==0) return -1;
	int id=++cnt;
	tree[id].date=pre[0];
	int i;
	for(i=0;mid[i]!=pre[0];i++) ;
	tree[id].left=makeTree(pre+1,mid,i);
	tree[id].right=makeTree(pre+i+1,mid+i+1,len-i-1);
	return id;
}

void mirror(int id){
	swap(tree[id].left,tree[id].right);
	if(tree[id].left!=-1) mirror(tree[id].left);
	if(tree[id].right!=-1) mirror(tree[id].right);
}

queue<int> q;
void bfs(){
	q.push(0);
	while(q.size()){
		Node t=tree[q.front()];
		q.pop();
		if(t.date!=pre[0]) printf(" ");
		printf("%d",t.date);
		if(t.left!=-1) q.push(t.left);
		if(t.right!=-1) q.push(t.right);
		
	}
}

void dfs(int id){
	cout<<tree[id].date<<" ";
	if(tree[id].left!=-1) dfs(tree[id].left);
	if(tree[id].right!=-1) dfs(tree[id].right);
}
int main(int argc, char** argv) {
	cin>>n;
	for(int i=0;i<n;i++) cin>>mid[i];
	for(int i=0;i<n;i++) cin>>pre[i];
	
	makeTree(pre,mid,n);
	mirror(0);
	bfs();
	return 0;
}