题目描述
二叉树是一种常用的数据结构。我们可以用大写的英文字母表示二叉树的节点。
如下:
B
/ \
/ \
C A
\
\
D
对于二叉树,有前序、中序和后序三种遍历方式。现在给你一棵二叉树的前序和中序遍历,请你求出这棵二叉树的后序遍历结果
输入
输入数据有多组,每组数据一行。
每行由两个字符串组成(每个字符串长度最大为26)。表示一棵二叉树的前序和中序遍历结果。
题目保证前序和中序遍历是合法的(即肯定可以确定一棵二叉树)。
输出
对于每组输入,输出对应的二叉树的后序遍历结果。
注意:本题输入输出都在控制台中,使用标准输入输出函数即可,不需要读写文件
样例输入
BCAD CBAD
ABDGKLRVWSXCEHMNFIOTUJPYQZ KGVRWLSXDBAMHNECTOUIFPYJZQ
样例输出
CDAB
KVWRXSLGDBMNHETUOIYPZQJFCA
参考代码
#include <stdio.h>
#include<string.h>
char xianxu[30],in[30];
void solve(int xianxuleft,int xianxuright,int inleft,int inright)
{
int root,leftsize,rightsize;
for (root=inleft;root<=inright;root++)
if(xianxu[xianxuleft]==in[root])break;
leftsize=root-inleft;
rightsize=inright-root;
if(leftsize>0)
solve(xianxuleft+1,xianxuleft+leftsize,inleft,root-1);
if(rightsize>0)
solve(xianxuleft+leftsize+1,xianxuright,root+1,inright);
printf("%c",in[root]);
}
int main()
{
while(~scanf("%s%s",xianxu,in))
{
int n=strlen(xianxu);
solve(0,n-1,0,n-1);
printf("n");
}
}
解析
暂无