题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入输出格式
输入格式： 2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式： 1行，表示一棵二叉树的先序。
输入输出样例
输入样例#1： BADC BDCA 输出样例#1： ABCD
【分析】 为二叉搜索树的学习练练手。 我们有中序排列（左-中-右）和后序排列（左-右-中），求的是前序排列（中-左-右）。
首先要知道的是，有前序（后序）和中序可以求后序（前序），但是只有前序和后序是不能求得中序的，证明从略。
后序遍历的特征是什么呢？根节点总是在最后被访问到。
那中序遍历的特征又是什么呢？根节点的左右两侧的点恰是它的左右子树。
我们拿一棵树来举例子：
首先这棵树的根是A（后序排列的最后一个），输出A；
然后在中序排列中找到A的位置，发现它左右各有三个点，分别是它的左右子树；
把中序排列左边三个点和后序排列的前三个点作为左子树去dfs，因为先序排列是中-左-右，所以先走左边；
[L]传入的中序是DEB，后序是EDB - 输出B，DE是左子树，同样操作；
[L]传入的中序是DE，后序是ED - 输出D，E是右子树，同样操作；
[R]传入的中序是E，后序是E - 输出E；
[R]传入的中序是FCG，后序是FGC - 输出C，F是左子树，同样操作，G是右子树，同样操作；
[L] 传入的中序是F，后序是F - 输出F；
[R] 传入的中序是G，后序是G - 输出G；
这样我们就完成了求先序遍历的过程。（上面略去了L/R子树为空的场合。
然后接下来我们就可以很简单地通过DFS来完成这道题了，因为求的是先序遍历，所以每次直接输出后序排列的最后一个点即可。没有必要去保存它。
在程序中我没有判断它有没有子树而是直接dfs了下去（为图方便）。因此，在dfs函数的开始要判断传入的字符串是否大于0。
另外，之前有人用了子串，但也没有必要，因为只访问而不修改，只要传给函数两个串的开始和结束下标就可以了。
代码如下，写起来很简单。
可以自己思考一下dfs中传入的四个参数为什么是那样。
【代码】
//洛谷 P1030 求先序排列 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; char mid[10],aft[10]; inline void dfs(int ml,int mr,int al,int ar) { int i,j,k; if(ml>mr || al>ar) return; printf("%c",aft[ar]); fo(i,ml,mr) if(mid[i]==aft[ar]) break; dfs(ml,i-1,al,al+i-ml-1); //递归构造左子树 dfs(i+1,mr,ar-mr+i,ar-1); //递归构造右子树 } int main() { int i,j,len; scanf("%s",mid); scanf("%s",aft); len=strlen(mid)-1; dfs(0,len,0,len); return 0; }