二叉树
时间： 1ms 内存：128M
描述：
二叉树是一种常用的数据结构。我们可以用大写的英文字母表示二叉树的节点。
如下：
B / \ / \ C A \ \ D对于二叉树，有前序、中序和后序三种遍历方式。 现在给你一棵二叉树的前序和中序遍历，请你求出这棵二叉树的后序遍历结果
输入：
输入数据有多组，每组数据一行。
每行由两个字符串组成（每个字符串长度最大为26）。表示一棵二叉树的前序和中序遍历结果。
题目保证前序和中序遍历是合法的（即肯定可以确定一棵二叉树）。
输出：
对于每组输入，输出对应的二叉树的后序遍历结果。
注意：本题输入输出都在控制台中，使用标准输入输出函数即可，不需要读写文件
示例输入：
BCAD CBAD
ABDGKLRVWSXCEHMNFIOTUJPYQZ KGVRWLSXDBAMHNECTOUIFPYJZQ
示例输出：
CDAB
KVWRXSLGDBMNHETUOIYPZQJFCA
提示：
参考答案（内存最优[752]）：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct BiTNod
{
char data;
struct BiTNod *lchild,*rchild;
}BTNode;
BTNode *creatBT(char *pre,char *in,int n)/*/pre[]存放先序序列，in[]存放中序序列，n为二叉树的节点数*/
{
BTNode *s;
char *p;
int k;
if(n<=0)
return NULL;
s=(BTNode *)malloc(sizeof(BTNode));/*/创建二叉树节点*s*/
s->data =*pre;
for(p=in;p<in+n;p++)
{
if(*p==*pre)
break;
}
k=p-in;
s->lchild =creatBT(pre+1,in,k);
s->rchild =creatBT(pre+k+1,p+1,n-k-1);
return s;
}
int preorder_l(BTNode *T)/*后序输出*/
{
if(T!=NULL)
{
preorder_l(T->lchild );
preorder_l(T->rchild );
printf("%c",T->data );
}
return 0;
}
int main()
{
char pre[30],in[30];
int n;
while(scanf("%s%s",pre,in)!=EOF)
{
n=strlen(pre);
preorder_l(creatBT(pre,in,n));
printf("\n");
}
return 0;
}参考答案（时间最优[0]）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iomanip>
#include <algorithm>
#include <queue>
#define INF 100000000
#define MAX 550
#define MAXN 130
#define MOD 9
using namespace std;
char pre[30],in[30];
void solve(int preleft,int preright,int inleft,int inright)
{
int root,leftsize,rightsize;
for(root=inleft;root<=inright;root++)
if(pre[preleft]==in[root])
break;
leftsize=root-inleft;
rightsize=inright-root;
if(leftsize>0)
solve(preleft+1,preleft+leftsize,inleft,root-1);
if(rightsize>0)
solve(preleft+leftsize+1,preright,root+1,inright);
printf("%c",in[root]);
}
int main()
{
while(~scanf("%s%s",pre,in))
{
int n=strlen(pre);
solve(0,n-1,0,n-1);
printf("\n");
}
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。