#1049 : 后序遍历
10000ms
1000ms
256MB
描述
在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树!
小Ho对这棵二叉树爱不释手,于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母,并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会,重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样,日子安稳的过了两天。
这天,小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果,但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上,小球和木棍等零件散落了一地!
小Ho损失了心爱的玩具,正要嚎啕大哭起来,所幸被小Hi发现了,劝说道:“别着急,这不是零件都还在么?拼起来不就是了?”
“可是我忘记了二叉树长什么样子了!”小Ho沮丧道。
“这个简单,你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么,利用这两个信息就可以还原出整棵二叉树来哦!”
“这样么?!!”小Ho止住了泪水,问道:“那要怎么做呢?”
没错!小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。
提示:分而治之——化大为小,化小为无
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。
每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。
对于100%的数据,满足二叉树的节点数小于等于26。
输出
对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。
样例输入
AB
BA
样例输出
BA
//给出一个二叉树的前序和中序遍历,还原二叉树并给出后序遍历;
#include
#include
#include
using namespace std;
#define N 51
char preTree[N],inTree[N];
struct ListNode{
char val;
struct ListNode *left,*right;
};
ListNode root;
ListNode* solve(char *preTree,int s1,int e1,char *inTree,int s2,int e2){
char str=preTree[s1];
int index=-1;
for(int i=s2;ival=str;
int left=index-s2;
int right=e2-index;
if(left>0)
root->left=solve(preTree,s1+1,s1+left,inTree,s2,index-1);
if(right>0)
root->right=solve(preTree,s1+left+1,e1,inTree,index+1,e2);
return root;
}
void postPrint(ListNode *root)
{
if(root!=NULL)
{
postPrint(root->left);
postPrint(root->right);
printf("%c",root->val);
}
}
int main()
{
int len;
while(scanf("%s",preTree)!=EOF)
{
scanf("%s",inTree);
len=strlen(preTree);
ListNode *tree=new ListNode();
tree=solve(preTree,0,len-1,inTree,0,len-1);
postPrint(tree);
printf("n");
}
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net