Start
原题题面: http://caioj.cn/problem.php?id=1037这博客从我学oi前就有,,,这么现在逐渐有种要变成算法博客的趋势 咱的老师把这道题讲了似乎许多遍了,不管了,上题解
分析题目
emmm……不知道大家还记不记得,有一年的初赛就有过已知两中遍历求另一种遍历,不过那个题目是到选择,你可以动手试试,这道就需要我们找规律了,首先我们要知道,有一下两种情况
- 已知前序与中序遍历,求后序遍历
- 已知后序与中序遍历,求前序遍历
ABDEHCFGI DBEHAFCIG根据前序遍历的特性,我们可以轻松的找到A为根,那么我们在两种遍历中去掉A
BDEH CFGI DBEH FCIG我们知道,中序遍历中,根节点左边是左子树部分,右边是有子树部分,让后我们就找到了左右子树 如果我们吧左子树在看成一个新的二叉树,那么继续搜下去,左后必然会精确到一个点,但是我们不知道要推多少次啊,怎么办?当然是递归
解析代码
先上代码
#include <cstdio>
#include <cstring>
using namespace std;
char a[110],b[110],x[110];//a字符串是前序遍历,b是中序遍历,x是后序遍历
int lx,k[110];
void dfs(int la,int ra,int lb,int rb){//la => 前序遍历左端点 la => 前序遍历左端点 ra => 前序遍历右端点 lb => 中序遍历左端点 rb => 中序遍历右端点
if(la>ra) return ;//等价与 if(lb>rb) return ; 如果你不理解,那么你可能还没有将题目读懂
int temp_a=k[a[la]]-lb;//为什么要减去lb?因为我们要去找到他的位置,然而位置的开始搜索可能并不是0
dfs(la+1,la+temp_a,lb,k[a[la]]-1);//往左子树找
dfs(la+temp_a+1,ra,k[a[la]]+1,rb);//往右子树找
x[lx++]=a[la];
}
int main(){
scanf("%s",a);
scanf("%s",b);//读入
int lena=strlen(a);
int lenb=strlen(b);//长度
for(int i=0;i<lenb;i++) k[b[i]]=i;//因为我们要知道前序遍历中的一位在中序遍历中的哪一位,然而搜索有太费时间,所以我们存一下
lx=0;//x字符串从0开始
dfs(0,lena-1,0,lenb-1);//开始的步骤
for(int i=0;i<lx;i++){
printf("%c",x[i]);
}
}
End
这道题目,,,,,,代码不难,思路特别的难,,所以,看脑子啦~ ]]>