Vijos1132:求二叉树的先序序列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

描述

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

格式

输入格式

第一行为二叉树的中序序列
第二行为二叉树的后序序列

输出格式

一行，为二叉树的先序序列

input:

BADC
BDCA

output:

ABCD

思路：先确定树根，再确定左子树与右子树的范围。

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=;
char in_order[MAXN];
char post_order[MAXN];
char pre_order[MAXN];
void build(int l1,int r1,int l2,int r2)
{
if(l1>r1)
return ;
char root=post_order[r2];
int p=l1;
while(in_order[p]!=root) p++;
printf("%c",root);
int cnt=p-l1;
build(l1,p-,l2,l2+cnt-);//左子树
build(p+,r1,l2+cnt,r2-);//右子树
}
int main()
{
scanf("%s",in_order);
scanf("%s",post_order);
int len=strlen(in_order);
build(,len-,,len-);
return ;
}

下面是利用中序遍历与前序遍历求后序遍历

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=;
char in_order[MAXN];
char pre_order[MAXN];
void build(int l1,int r1,int l2,int r2)
{
if(l1>r1||l2>r2)
return ;
char root=pre_order[l2];
int p=l1;
while(in_order[p]!=root) p++;
int cnt=p-l1;
build(l1,p-,l2+,l2+cnt);
build(p+,r1,l2+cnt+,r2);
printf("%c",root);
}
int main()
{
scanf("%s",in_order);
scanf("%s",pre_order);
int len=strlen(in_order);
build(,len-,,len-);
return ;
}