hiho#1049 : 后序遍历( nyoj848 STBE)
时间限制: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; }
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻