首页 > 代码库 > nyoj756_重建二叉树_先序遍历
nyoj756_重建二叉树_先序遍历
重建二叉树
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
- 题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。
- 输入
- 输入有多组数据（少于100组），以文件结尾结束。
每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。 - 输出
- 每组输出数据单独占一行，输出对应得先序序列。
- 样例输入
ACBFGED ABCDEFGCDAB CBAD
- 样例输出
DBACEGFBCAD
- 来源
- 原创
- 上传者
- TC_黄平
- 解题思路：因为之前做过两个输出后序遍历的，所以用之前的方法做的，但递归的时候想错了，结果差点以为这种方法做不出来。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;char subs[30];char tmp[30];char in[30];int t[30]={0};void traverse(int s1,int s2,int n){ if(n==1){ printf("%c",tmp[s1]); return ; } if(n<=0){ return ; } t[s1]=1; int i; for(i=0;tmp[s1]!=in[s2+i];i++); printf("%c",tmp[s1]); traverse(s1+(n-i),s2,i);//第一个参数应该是s1+（n-i） traverse(s1+1,s2+i+1,n-i-1);}int main(){ while(scanf("%s %s",subs+1,in+1)!=EOF){ memset(t,0,sizeof(t)); int cou=1; int len=strlen(subs+1); for(int i=len;i>0;i--){ tmp[cou++]=subs[i]; } traverse(1,1,len); printf("\n"); } return 0;}
nyoj756_重建二叉树_先序遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。