分类
OI

Caioj 1034:二叉树的后序遍历

Start


原题题面: http://caioj.cn/problem.php?id=1037
这博客从我学oi前就有,,,这么现在逐渐有种要变成算法博客的趋势 咱的老师把这道题讲了似乎许多遍了,不管了,上题解

分析题目


emmm……不知道大家还记不记得,有一年的初赛就有过已知两中遍历求另一种遍历,不过那个题目是到选择,你可以动手试试,这道就需要我们找规律了,首先我们要知道,有一下两种情况
  1. 已知前序与中序遍历,求后序遍历
  2. 已知后序与中序遍历,求前序遍历
这两种状况是有唯一解的,其他的答案可能就会有多种 那么我们先看样例
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


这道题目,,,,,,代码不难,思路特别的难,,所以,看脑子啦~ ]]>

“Caioj 1034:二叉树的后序遍历”上的1条回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注