#include <bits/stdc++.h> using namespace std; typedef int typeData; const int maxn = 1100; int pre[maxn]; //记录前序遍历 int in[maxn]; //记录中序遍历 struct node{ typeData data; node* leftChild; node* rightChild; node(){ leftChild = NULL; rightChild = NULL; } };

void postorder(node *root, node *flag){ //输出后序遍历 if(root == NULL) return; postorder(root->leftChild, flag); postorder(root->rightChild, flag);

printf("%d", root->data);
 if(root != flag)
     printf(" ");

} //传入先序遍历起始位置，中序遍历起始位置 node* create(int preL, int preR, int inL, int inR){ if(preL > preR) //如果前序遍历中没有数值返回NULL return NULL; node* root = new node(); //建立新结点，其权值为，当前先序遍历的首位，即当前树根结点 root->data = pre[preL]; int k; //k记录根结点在中序遍历中的位置 for(k = inL; k < inR; k++){ //在中序遍历中寻找根结点位置 if(pre[preL] == in[k]) break; } int numLeft = k - inL; //计算左子树长度 root->leftChild = create(preL + 1, preL + numLeft, inL, k - 1); //递归建立左子树 //先序遍历中左子树区域为根结点的下一位到左子树起始点加左子树长度 //中序遍历中左子树区域为中序遍历首位到根结点之前 root->rightChild = create(preL + numLeft + 1, preR, k + 1, inR); //递归建立右子树 //先序遍历中右子树区域为左子树末尾的下一位到先序遍历末位 //中序遍历中右子树区域为根结点后一位到中序遍历末位 return root; } int main() { int n; while(cin >> n){ memset(pre, 0, sizeof(pre)); memset(in, 0, sizeof(in)); for(int i = 0; i < n; i++){ scanf("%d", &pre[i]); //输入先序遍历 } for(int i = 0; i < n; i++){ //输入中序遍历 scanf("%d", &in[i]); } node* root = create(0, n - 1, 0, n - 1); //建树 postorder(root, root); //输出后序遍历 printf("\n"); } }