POJ_2255_Tree Recovery
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 12342 | Accepted: 7712 |
Description
This is an example of one of her creations:
D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F
To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!
Input
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
Input is terminated by end of file.
Output
Sample Input
DBACEGF ABCDEFG
BCAD CBAD
Sample Output
ACBFGED
CDAB3
题解:在前序中取根节点,在中序中找到该节点,其左边为该根节点左子树,右边为右子树
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char fro[],mid[];
void beh(int fs,int fe,int ms,int me)
{
if(fs==fe)
{
cout<<fro[fs];
return;
}
if(fs>fe||ms>me)
return;
char root=fro[fs];
int i;
for(i=ms;i<me;i++)
if(root==mid[i])
break;
int len=i-ms;
beh(fs+,fs+len,ms,i-);
beh(fs+len+,fe,i+,me);
cout<<root;
}
int main()
{
while(scanf("%s%s",fro,mid)!=EOF)
{
int len=strlen(fro);
beh(,len-,,len-);
cout<<endl;
}
return ;
}
最新文章
- vi/vim使用小结
- Linux 标准目录结构
- IIS7.0设置404错误页,返回500状态码
- 通过JS判断联网类型和连接状态
- css之marquee,让你的文字跳起来
- Delphi利用Webbrowser登陆QQ群文档
- Android Ant 和 Gradle 打包流程和效率对照
- FZUOJ Problem 2178 礼品配送
- java映射(map用法)
- 【JAVA零基础入门系列】Day2 Java集成开发环境IDEA
- springdata jpa 原始sql的使用
- 关于shiro安全框架实现同一用户同一时刻仅可在一个地址登录的技术实现
- MySQL5.7单实例二进制包安装方法
- [Django] Window上通过IIS发布Django网站
- 024 SpringMvc的异常处理
- Spark机器学习(3):保序回归算法
- vue-cli watch/timer
- 关于xmlhttp会使用ie的缓存的问题及解决
- galera mariadb集群恢复策略
- 05 Go 1.5 Release Notes
热门文章
- java设计模式 -------- 行为模式 之 策略模式(4)
- .net的程序的逆向分析。
- Linq To Sql 增改删
- 2016/1/22 1, 1-100 放集合 特定对象移除 2,List集合和Set集合是否可以重复添加
- ios32---线程的状态
- C#与excel互操作的错误无法将类型为“Microsoft.Office.Interop.Excel.ApplicationClass”的 COM 对象强制
- HQL 查询数据 (获取页面输入的查询条件字段)
- VS2015 razor 提示一闪而过
- mybatis中各种数据的映射类型
- A brief preview of the new features introduced by OpenGL 3.3 and 4.0