1138 Postorder Traversal （25 分）

给出前序遍历和中序遍历，输出后序遍历和层序遍历。
这是遍历的基本操作，还是要牢牢掌握才行。

#include<cstdio>
#include<vector> 
#include<queue>
#include<iostream>
using namespace std;
const int maxn=5e4+5;
int n;
vector<int> pre,in,post;
struct node{
	int data;
	node *left, *right;
	node(int x):data(x),left(NULL),right(NULL){}
};
void create(node* &root, int preL,int  preR, int inL, int inR){
	if(preL > preR) return;
	if(root == NULL)
		root = new node(pre[preL]);  //这个地方容易写错 
	int k=inL;
	while(root->data != in[k]){
		k++;
	}
	int left = k - inL;
	create(root->left,preL+1, preL+left,inL, k-1);
	create(root->right,preL+left+1,preR, k+1, inR);
}

void postorder(node* root){
	if(root == NULL) return;
	postorder(root->left);
	postorder(root->right);
	post.push_back(root->data);
}

int main(){
	int x;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		pre.push_back(x);
	}
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		in.push_back(x);
	}
	node* root = NULL;
	create(root,0,pre.size()-1,0,in.size()-1);
	postorder(root);
	printf("%d\n",post[0]);
	return 0;
}