这是我今天做网易笔试题最后的编程题所碰到的问题。由于考试时时间比较紧，写的代码难免有瑕疵。
sample input
ABDGCEF
DGBAECF
sample output
GDBEFCA
思路：比较容易想到的方法是把它还原为二叉树再进行后序遍历。不过这样就比较麻烦了。下面的方法跳过建树的过程直接求后序遍历的。时间复杂度为O(n^2),空间复杂度为O(n)。当然这不是最优的，本人已经想到改进的方法，可以把时间复杂度降到O(nlogn)。不过由于懒惰，所以就苟且用这个吧。实际上有简短的递归方法。所以仅当做一种另类的想法记录一下。
用一个order数组存中序遍历中的字符在后序遍历中的顺序，从大到小。比如sample input中所得的order为：5 6 4 0
3 1 2。
直接用上面的例子说明算法过程：
order=0 0 0 0 0 0 0
对于str1中的A，找出它在str2中的位置为4，它左右order的值都和4位置的order的值相同，说明它有左、右子树
改变order的值为：
2 2 2 0 1 1 1
对于str1中的B，找出它在str2中的位置3，它左order的值和当前order值相同，说明它有左子树，
改变order的值为：
3 3 2 0 1 1 1
对于str1中的D，找出它在str2中的位置1，改变order的值为：
3 4 2 0 1 1 1
对于str1中的G，找出它在str2中的位置2，改变order的值为：
3 4 2 0 1 1 1
对于str1中的C，找出它在str2中的位置6，改变order的值为：
5 6 4 0 3 1
2
....
处理完后就得到order的值为5 6 4
0 3 1 2，恰好是后序遍历中str2的字符被反问到的顺序（从大到小）。
代码：
#include <iostream>
#include <string>
using namespace std;
const int maxn=100;
int find(char c,char str[])
{
int
len=strlen(str);
for (int
i=0;i<len;i++)
if (c==str[i]) return i;
return
len;
}
int main()
{
char
str1[maxn],str2[maxn],str[maxn];
cin>>str1>>str2;//输入前、中序遍历
int
len=strlen(str1);
if
(len!=strlen(str2)) return -1;
int
order[maxn]={0};//order初始化为0
for (int
i=0;i<len;i++)
{
int k=find(str1[i],str2);//找到前序第i个字符在中序字符中的位置
int t=0;
if (k>0 &&
order[k-1]==order[k]) t++;//有左子树
if (k<len-1 &&
order[k+1]==order[k]) t++;//有右子树
for (int j=0;j<len;j++) if
(order[j]>order[k]) order[j]+=t;//对于上面一层的加深层数
if (t==2)
{
for (int j=k-1;j>=0;j--) if
(order[j]>=order[k]) order[j]+=t; else
break;//左子树被访问顺序会比右子树快1，所以下面order[j]+=t-1;
for (int j=k+1;j<len;j++) if
(order[j]>=order[k]) order[j]+=t-1; else
break;
continue;
}
if (t==1)
{
if (k>0 &&
order[k-1]==order[k])//有左子树
for (int j=k-1;j>=0;j--) if (order[k]==order[j])
order[j]+=t; else break;
if (k<len-1 &&
order[k+1]==order[k])//有右子树
for (int j=k+1;j<len;j++) if (order[k]==order[j])
order[j]+=t; else break;
}
}
for (int
i=0;i<len;i++)//映射中序为后序
str[len-order[i]-1]=str2[i];
str[len]=0;
cout<<str<<endl;//输出
return
0;
}