题目传送门

一、理解与感悟

1、已知前序+中序，求后序

P1827 [USACO3.4]美国血统 American Heritage
https://www.luogu.com.cn/problem/P1827

思路：
（1）、二叉树的遍历，就是一个深度优先搜索的过程:
前序

void pre_order(int x){
 printf("%d\n",x);
 if(t[x].left) pre_order(t[x].left);
 if(t[x].right) pre_order(t[x].right);
}

中序

void in_order(int x){
 if(t[x].left) in_order(t[x].left);
 printf("%d\n",x);
 if(t[x].right) in_order(t[x].right);
}

后序

void post_order(int x){
 if(t[x].left) post_order(t[x].left);
 if(t[x].right) post_order(t[x].right);
 printf("%d\n",x);
}

说白了，套路基本一样，就是三步：输出当前结点，递归左子树，递归右子树。根据输出顺序不同，产生了三种遍历方式。

2、已知后序+中序，求前序

P1030 [NOIP2001 普及组] 求先序排列
https://www.luogu.com.cn/problem/P1030