标签：二叉树

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?因为我们要去找到他的位置,然而位置的开始搜索可能并不是０
    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

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