【PAT甲级】1119 Pre- and Post-order Traversals (30分)(已知先序后序输出是否二叉树唯一并输出中序遍历)
2024-10-08 06:16:54
题意:
输入一个正整数N(<=30),接着输入两行N个正整数第一行为先序遍历,第二行为后续遍历。输出是否可以构造一棵唯一的二叉树并输出其中一颗二叉树的中序遍历。
trick:
输出完毕中序遍历后须换行,否则所有测试点格式错误。
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int pre[],post[];
map<int,int>mp;
int flag;
vector<int>ans;
void dfs(int prel,int prer,int postl,int postr){//先序遍历起点,先序遍历终点,后序遍历起点,后序遍历终点
if(prel==prer){//根节点
ans.emplace_back(pre[prel]);
return ;
}
int x=mp[post[postr-]];//找到后序遍历中根节点前一个结点在先序遍历中的位置,这个结点即为右子树的根节点
if(x-prel>){//存在左子树
dfs(prel+,x-,postl,postl+x-prel-);//划分左子树
//先序遍历中:左子树起点为去掉根节点,左子树终点为先序遍历中右子树根节点前一个结点;
//后序遍历中:左子树起点不变,左子树终点为起点加上先序遍历中终点和起点的差
ans.emplace_back(pre[prel]);//左子树的根节点
dfs(x,prer,postl+x-prel-+,postr-);//划分右子树
//先序遍历中:右子树起点为x,右子树终点为最后一个结点;
//后序遍历中:右子树起点为左子树终点+1,右子树终点为去掉根节点
}
else{//不存在左子树,那么这个结点可以作为左右结点任一,构造结果因此不唯一
flag=;//标记
ans.emplace_back(pre[prel]);//子树的根节点
dfs(x,prer,postl+x-prel-+,postr-);//把剩余结点当作右子树,处理方法和划分右子树相同
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=;i<=n;++i){
cin>>pre[i];
mp[pre[i]]=i;//记录点序号在先序遍历中出现的位置
}
for(int i=;i<=n;++i)
cin>>post[i];
dfs(,n,,n);//对先序遍历进行分割
if(flag==)
cout<<"Yes\n";
else
cout<<"No\n";
cout<<ans[];
for(int i=;i<ans.size();++i)
cout<<" "<<ans[i];
cout<<"\n";
return ;
}
最新文章
- Java中的URL类
- 单例设计模式全局缓存accessToken
- C# DateTime转Json汇总
- Javascript异步编程方法总结
- HDU4495 Rectangle
- gauss消元
- ASP.NET数据验证控件的常用的属性
- ApiCloud重新定义移动应用开发
- HTML基本操作
- UVa 11988 (数组模拟链表) Broken Keyboard (a.k.a. Beiju Text)
- RavenScheme简介
- Oracle char 查询问题
- ThinkPHP 3.2 模板使用函数
- 统计难题(trie树)
- Missing artifact net.sf.json-lib:json-lib:jar:2.2.3:compile
- 本地文件与服务器文件同步shell脚本。
- 微信小程序开发之详解生命周期方法
- Angular5 宏观把控
- Raptor入门与安装
- 【转载】c++中浅复制与深复制