这题通过率蛮高的，没有坑，但是如果不知道如何通过后序和中序来还原一个二叉树的话，这题可以说是无从下手。这题对我来说还算比较难的，之前没做过树的题。算是一个新知识。
1 #include <iostream>
2 #include<vector>
3 #include<algorithm>
4 using namespace std;
5 struct node{
6 int index,value;
7 };
8 bool cmp(node a,node b){
9 return a.index<b.index;
10 }
11 vector<int> po(100);
12 vector<int> in(100);
13 vector<node> ans;
14 void pre(int root,int start,int end,int index){//root,根节点在后序列表中的位置
15 if(start>end) return;
16 int i=start; //i是根节点在中序中的位置
17 while(i<end&&in[i]!=po[root]) i++;//在中序的[start,end]中找根节点
18 node a;
19 a.index=index;
20 a.value=po[root];
21 ans.push_back(a);
22 /* 如何在后序列表中找到左子树的根，通过右子树的个数来确定
23 x为左子树的根的位置，y为右子树的根的位置
24 x+右子树个数=y
25 右子树个数易确定为end-(i+1)+1=end-i */
26 pre(root-1-end+i,start,i-1,2*index+1);
27 pre(root-1,i+1,end,2*index+2);
28 }
29 int main()
30 { int n;
31 cin>>n;
32 po.resize(n);
33 in.resize(n);
34 for(int i=0;i<n;i++){
35 cin>>po[i];
36 }
37 for(int i=0;i<n;i++){
38 cin>>in[i];
39 }
40 pre(n-1,0,n-1,0);
41 sort(ans.begin(),ans.end(),cmp);
42 for(int i=0;i<n;i++){
43 if(i!=n-1)
44 cout<<ans[i].value<<" ";
45 else
46 cout<<ans[i].value;
47 }
48 return 0;
49 }