hihoCoder 1049 : 后序遍历（二叉树遍历）

超、凢脫俗 2024-02-17 21:59 10阅读 0赞

#### \#1049 : 后序遍历 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

##### 描述 #####

在参与过了美食节之后，小Hi和小Ho在别的地方又玩耍了一阵子，在这个过程中，小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的[二叉树][Link 1]！

小Ho对这棵二叉树爱不释手，于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母，并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会，重新巩固了一下小Ho关于[二叉树遍历][Link 2]的基础知识~就这样，日子安稳的过了两天。

这天，小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果，但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上，小球和木棍等零件散落了一地！

小Ho损失了心爱的玩具，正要嚎啕大哭起来，所幸被小Hi发现了，劝说道：“别着急，这不是零件都还在么？拼起来不就是了？”

“可是我忘记了二叉树长什么样子了！”小Ho沮丧道。

“这个简单，你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么，利用这两个信息就可以还原出整棵二叉树来哦！”

“这样么？！！”小Ho止住了泪水，问道：“那要怎么做呢？”

没错！小Ho在这一周遇到的问题便是：**给出一棵二叉树的前序和中序遍历的结果，还原这棵二叉树并输出其后序遍历的结果。**

##### 输入 #####

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为一个由大写英文字母组成的字符串，表示该二叉树的前序遍历的结果。

每组测试数据的第二行为一个由大写英文字母组成的字符串，表示该二叉树的中序遍历的结果。

对于100%的数据，满足二叉树的节点数小于等于26。

##### 输出 #####

对于每组测试数据，输出一个由大写英文字母组成的字符串，表示还原出的二叉树的后序遍历的结果。

样例输入

AB
    BA

样例输出

分析：递归建树，然后输出

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=26+2;
    char pre_order[maxn];
    char mid_order[maxn];
    char lson[maxn],rson[maxn];
    
    char build(int l,int r,int l2,int r2){  //l,r先序，l2,r2中序 
    	if(l>r)return '0';
        char root=pre_order[l];
        
        int p=l2;
        while(mid_order[p]!=pre_order[l])p++;
        
        lson[root-'A']=build(l+1,(p-l2)+l,l2,p-1);
        rson[root-'A']=build((p-l2)+l+1,r,p+1,r2);
        return root;
    }
    
    void bianli(char root){
    	if(root=='0')return ;
    
        bianli(lson[root-'A']);
        bianli(rson[root-'A']);
        printf("%c",root);
    }
    
    int main(){
    	while(scanf("%s%s",pre_order,mid_order)==2){
    		int len=strlen(pre_order);
    		build(0,len-1,0,len-1);
    		
    		bianli(pre_order[0]);
    		printf("\n");
    	}
    	return 0;
    }

[Link 1]: http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
[Link 2]: http://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86