后序和中序

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

struct node {
	int data;
	node* lchild;
	node* rchild;
	node(int a):data(a),lchild(NULL),rchild(NULL) {
	}
};

const int Max=50;
int n,P[Max],I[Max];

node* create(int p1,int p2,int i1,int i2) {
	if(p1>p2) {
		return NULL;
	}
	node* root=new node(P[p2]);
	int k;
	for(k=i1; k<=i2; k++) {
		if(I[k]==P[p2]) {
			break;
		}
	}
	int num=k-i1;
	root->lchild=create(p1,p1+num-1,i1,k-1);
	root->rchild=create(p1+num,p2-1,k+1,i2);
	return root;
}

int num=0;
void BFS(node* root) {
	queue<node*> q;
	q.push(root);
	while(!q.empty()) {
		node* now=q.front();
		q.pop();
		cout<<now->data;
		num++;
		if(num<n) cout<<" ";
		if(now->lchild!=NULL) {
			q.push(now->lchild);
		}
		if(now->rchild!=NULL) {
			q.push(now->rchild);
		}
	}
}

int main() {
	while(cin>>n) {
		for(int i=0; i<n; i++) {
			cin>>P[i];
		}
		for(int i=0; i<n; i++) {
			cin>>I[i];
		}
		node* root=create(0,n-1,0,n-1);
		BFS(root);
	}
	return 0;
}