首页 > 考试 > 等级考试 > 其他 > 正文
hiho#1049 : 后序遍历( nyoj848 STBE)
2016-05-02       个评论    来源:苏苏爱自由  
收藏    我要投稿
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树

小Ho对这棵二叉树爱不释手,于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母,并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会,重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样,日子安稳的过了两天。

这天,小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果,但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上,小球和木棍等零件散落了一地!

小Ho损失了心爱的玩具,正要嚎啕大哭起来,所幸被小Hi发现了,劝说道:“别着急,这不是零件都还在么?拼起来不就是了?”

“可是我忘记了二叉树长什么样子了!”小Ho沮丧道。

“这个简单,你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么,利用这两个信息就可以还原出整棵二叉树来哦!”

“这样么?!!”小Ho止住了泪水,问道:“那要怎么做呢?”

没错!小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。

每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。

对于100%的数据,满足二叉树的节点数小于等于26。

输出

对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。

样例输入
AB
BA
样例输出
BA
着实看了一下午 唉 理解的难啊

 

理论上自己是会的 翻译成代码 就变了味了抓狂

步骤

1.找到根节点 左子树 右子树

2.递归左子树

3.递归右子树

4.输出当前根节点

 

#include 
#include 
void get_end(char *pre,char *mid,char *end,int len)
{
	if(len==0)
	return ;
	int root=strchr(mid,pre[0])-mid;
	int leftlen=root;//左子树的长度 
	int rightlen=len-leftlen-1;//右子树的长度 (也要减去根节点) 
	/*
	因为len 的变化是从leftlen->0  rightlen->0 
	在左子树递归时 保存后序的end 是从0开始
	在右子树递归时 保存后序的end 要从end+leftlen开始
	在这里理解了很久 所以加上注释 
	*/ 
	get_end(pre+1,mid,end,leftlen);//左子树递归  
	get_end(pre+leftlen+1,mid+leftlen+1,end+leftlen,rightlen);//右子树递归 
	/*
	根据先序遍历规则  根节点+左子树序列+右子树序列
	所以每一个pre[0] 都是当前树的根节点 
	而后序遍历规则  左子树序列+右子树序列+根节点
	所以end[len-1]=pre[0]  懂了吧~ 
	*/
	end[len-1]=pre[0]; 
}
int main()
{	
	char a[30];
	char b[30];
	while(~scanf("%s %s",a,b))
	{
		char end[30];
		memset(end,0,sizeof(end));
		get_end(a,b,end,strlen(a));
		puts(end);
	}
	return 0;
}


 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:笔试题43. LeetCode OJ (30)
下一篇:最后一页
相关文章
图文推荐
文章
推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站