1070 - 复原二叉树
小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。
题目输入
输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。
题目输出
对于每组输入，输出对应的二叉树的后续遍历结果。
输入/输出样例
题目输入
DBACEGF ABCDEFG BCAD CBAD
题目输出
ACBFGED CDAB
C语言解答
#include <stdio.h> #include <string.h> void build(char *pre,char *in,int len){ if (len<=0) { return ; } int pos=strchr(in,*pre)-in; build(pre+1,in,pos); build(pre+pos+1,in+pos+1,len-pos-1); printf("%c",*pre); } int main(){ char pre[1000],in[1000]; // freopen("1.txt","r",stdin); while (scanf("%s %s",pre,in)!=EOF) { build(pre,in,strlen(pre)); printf("\n"); } // fclose(stdin); return 0; }
C++解答
#include<cstdio> #include<iostream> #include<string> using namespace std; struct BT { char data; BT *lchild,*rchild; }; BT *build(string preorder,string inorder) { BT *root; int p; if(!preorder.length()) root=NULL; else { root=new BT; root->data=preorder[0]; p=inorder.find(root->data); root->lchild=build(preorder.substr(1,p),inorder.substr(0,p)); root->rchild=build(preorder.substr(1+p),inorder.substr(p+1)); } return root; } void postorder(BT *root) { if(root) { postorder(root->lchild); postorder(root->rchild); putchar(root->data); } } int main() { string preorder,inorder; BT *root; while(cin>>preorder>>inorder) { root=build(preorder,inorder); postorder(root); printf("\n"); } return 0; }