题意:

输入一个正整数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 ;
}

最新文章

  1. Java中的URL类
  2. 单例设计模式全局缓存accessToken
  3. C# DateTime转Json汇总
  4. Javascript异步编程方法总结
  5. HDU4495 Rectangle
  6. gauss消元
  7. ASP.NET数据验证控件的常用的属性
  8. ApiCloud重新定义移动应用开发
  9. HTML基本操作
  10. UVa 11988 (数组模拟链表) Broken Keyboard (a.k.a. Beiju Text)
  11. RavenScheme简介
  12. Oracle char 查询问题
  13. ThinkPHP 3.2 模板使用函数
  14. 统计难题(trie树)
  15. Missing artifact net.sf.json-lib:json-lib:jar:2.2.3:compile
  16. 本地文件与服务器文件同步shell脚本。
  17. 微信小程序开发之详解生命周期方法
  18. Angular5 宏观把控
  19. Raptor入门与安装
  20. 【转载】c++中浅复制与深复制

热门文章

  1. Notability
  2. 本地建立Minecraft服务器
  3. LAMP搭建随笔
  4. 深入浅出Mybatis系列九-强大的动态SQL
  5. 什么人适合学习Django?
  6. 剑指offer-面试题15-二进制中1的个数-位运算
  7. list=null和list.size=0的区别
  8. Linux下快速删除大量小文件引起的磁盘inode(目录索引)过满
  9. 输出《Harry Potter and the Sorcerer&#39;s Stone》英文i的字母数量并排序
  10. centos系统mongodb安装