codevs——1013 求先序排列-白红宇

codevs——1013 求先序排列

阅读量：5907 次

发布时间：2019-06-19

本文共 886 字，大约阅读时间需要 2 分钟。

1013 求先序排列

2001年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述

Description

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入描述

Input Description

两个字符串，分别是中序和后序（每行一个）

输出描述

Output Description

一个字符串，先序

样例输入

Sample Input

BADC

BDCA

样例输出

Sample Output

ABCD

代码：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define N 100000#define maxn 123456using namespace std;char a[N],b[N];int c[N],d[N]; void dfs(int l,int r,int L,int R){ printf("%c",b[R]); if(d[R]>l) dfs(l,d[R]-1,L,d[R]-l+L-1);//说明他有左子树，那么对她的左子树进行查找 //对一棵树来说，它的左子树的最左端一定是L,最右端就是 //它的根所在的地方（在中序排序中）+减去中序排序的左端点——这是求出了他的左子树的长度 //那他的在后续排序中的最右端是在后续排序的左端+他的左子树的长度 if(d[R]