poj 2255 Tree Recovery 分治
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
CDAB
Source
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll __int64
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=1e5+,M=1e6+,inf=1e9+;
char a[],b[];
char ans[N];
void dfs(char *a,char *b,char *c,int len)
{
if(len<=)
return;
int n=strlen(b),pos=;
for(int i=;i<n;i++)
{
if(b[i]==a[])
{
pos=i;
break;
}
}
int l=pos;
int r=len-pos-;
dfs(a+,b,c,l);
dfs(a+l+,b+l+,c+l,r);
c[len-]=a[];
}
int main()
{
int x,y,z,i,t;
while(~scanf("%s%s",a,b))
{
x=strlen(a);
dfs(a,b,ans,x);
ans[x]=;
cout<<ans<<endl;
}
return ;
}
最新文章
- 闭包Closures
- JS基础知识(-)
- Compute Mean Value of Train and Test Dataset of Caltech-256 dataset in matlab code
- 【BZOJ】【2179】FFT快速傅里叶
- Swift - 使用CoreLocation实现定位(经纬度、海拔、速度、距离等)
- Linq中join &; group join &; left join 的用法
- nautilus出现一闪而过现象
- IBM服务器安装Ubuntu Linux server 64以及网络配置
- K数和问题
- DRF之项目搭建
- linux下怎样批量更改文件后缀名
- java学习之路--String类方法的应用
- Python3学习笔记17-类与实例
- serial -1
- 2016 移动应用质量大数据报告--转自腾讯Bugly
- Ubuntu18.04下的音频录制和编辑软件Ardour及QjackCtl(jackd gui)
- 关于YII中layout中的布局和view中数据的关系
- CSU 1240 低调,低调。
- python django-admin startproject django-admin命令未找到
- 【WXS全局对象】Math
热门文章
- AttributeError: &#39;NoneType&#39; object has no attribute &#39;append&#39;
- Linux命令(基础1)
- (0.2.2)如何下载mysql数据库(二进制、RPM、源码、YUM源)
- 010-Shell 输入/输出重定向
- redis实现cache系统实践(六)
- Charles 抓包工具的使用
- SQL Server 数据分页查询
- cocoon + carrierwave 多图片上传用法
- Lua 基础总结
- Spring MVC 知识总结