ZOJ3965 Binary Tree Restoring
2024-09-02 01:42:44
ZOJ3965 给定一颗二叉树的两种DFS序列 输出一种可能的二叉树的结构。
考察树的递归性质,不要想的太复杂。
当前节点在两个串中后面的节点假如不同则能确认两个子树,如果相同则把下个点作当前点的一个儿子。如果子树中还有未连根的点则接到当前点下。son数组表示每个点的子树有多少个点。pos数组记录每个数在每个序列中的位置。dfs中p1,p2指向同一个数
lim1,lim2表示当前点子树可能最大的子树范围。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector> using namespace std;
#define maxn 110000
int n,fa[maxn];
int s1[maxn],s2[maxn];
int pos1[maxn],pos2[maxn];
int vis[maxn],son[maxn];
void dfs(int p1,int p2,int lim1,int lim2)
{
//printf("%d %d %d %d\n:::::\n",p1,lim1,p2,lim2);
//system("pause");
int now=s1[p1];
if(vis[now]) return;
vis[now]=1;
if(p1<=0||p1>n) return ;
if(p2<=0||p2>n) return ;
if(lim1<=0) return ;
if(lim2<=0) return ;
if(p1>lim1||p2>lim2) return;
son[now]=1;
if(lim1==p1||lim2==p2) return;
int r1=lim1,r2=lim2;
if(s1[p1+1]!=s2[p2+1]&&p1+1<=lim1&&p2+1<=lim2)
{
int len=0;
if(!fa[s1[p1+1]])
{
fa[s1[p1+1]]=now;
r1=pos1[s2[p2+1]]-1;
len=r1-p1;
dfs(p1+1, pos2[ s1[p1+1] ] , r1 ,pos2[ s1[p1+1] ]+len-1 );
son[now]+=son[ s1 [p1+1] ];
}
if(!fa[s2[p2+1]])
{
fa[s2[p2+1]]=now;
r2=pos2[s1[p1+1]]-1;
len=r2-p2;
dfs( pos1[s2[p2+1]] , p2+1, pos1[s2[p2+1]]+len-1, r2 );
son[now]+=son[ s2 [p2+1] ];
}
}
else if(s1[p1+1]==s2[p2+1]&&p1+1<=lim1&&p2+1<=lim2)
{
fa[ s1[p1+1] ] = now;
dfs(p1+1,p2+1,lim1,lim2);
son[now]+=son[ s1[p1+1] ];
int nt=p1+son[s1[p1+1]]+1;
if(son[now]<lim1-p1+1)
{
fa[s1[nt]]=now;
dfs(nt,pos2[s1[nt]],lim1,lim2);
son[now]+=son[s1[nt]];
}
}
} int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
memset(fa,0,sizeof(fa));
memset(vis,0,sizeof(vis));
memset(son,0,sizeof(son));
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(pos1,0,sizeof(pos1));
memset(pos2,0,sizeof(pos2));
for(int i=1;i<=n;i++) scanf("%d",&s1[i]),pos1[s1[i]]=i;
for(int i=1;i<=n;i++) scanf("%d",&s2[i]),pos2[s2[i]]=i;
dfs(1,1,n,n);
for(int i=1;i<n;i++) printf("%d ",fa[i]);
printf("%d\n",fa[n]);
}
return 0;
}
最新文章
- oc学习之路----scrollView的代理模式
- 收货MIGO
- 50个很棒的Python模块
- Effective java -- 3 类和接口
- WEB前端:浏览器(IE+Chrome+Firefox)常见兼容问题处理--01
- ELK-ElasticSearch索引详解
- Intellij 代理抛出异常错误: java.rmi.server.ExportException: Port already in use: 1099,端口被占用
- POJ 1986 Distance Queries(LCA Tarjan法)
- [译]课程 1: 使用 Quartz
- redis缓存服务器集群搭建
- Msfvenom学习总结
- C# 调用程序集方法
- asp.net mvc5轻松实现插件式开发
- 使用PHP打造QQ空间神奇图片
- 通过USB连接越狱iPhone,SSH进入设备
- F# 图形数学基础。
- Docker实战(四)之Docker数据管理
- HDU 1789 Doing Homework again(非常经典的贪心)
- hadoop集群的配置文件
- web.py使用要点
热门文章
- Hadoop-2.7.1伪分布--安装配置hbase 1.1.2
- scrapy爬取简书整站文章
- LeetCode(64) Minimum Path Sum
- 杭电 2803 The MAX(sort)
- Python文件处理(txt、csv文件读取)
- jQuery学习之------元素样式的操作
- ssh远程登录
- 51nod 1010 只包含因子2 3 5的数 &;&; poj - 1338 Ugly Numbers(打表)
- 51nod 1126 求递推序列的第N项 &;&; hdu - 1005 Number Sequence (求周期)
- cogs 48. [NOIP2007] 字符串的展开