链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456


题目:

给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式:

输入第一行给出一个正整数N(≤),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

4 1 6 3 5 7 2

思路:
模板题

代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue> using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int maxn=;
int n;
int mid[maxn],po[maxn]; struct node{
int l,r;
}T[maxn]; int mid_po_build(int la,int ra,int lb,int rb){
if(la>ra) return ;
int rt=po[rb];
int p1=la,p2;
while(mid[p1]!=rt) p1++;
p2=p1-la;
T[rt].l=mid_po_build(la,p1-,lb,lb+p2-);
T[rt].r=mid_po_build(p1+,ra,lb+p2,rb-);
return rt;
} void dfs(int rt){
queue<int>Q;
vector<int>v;
Q.push(rt);
while(!Q.empty()){
int w=Q.front();
Q.pop();
v.push_back(w);
if(T[w].l!=) Q.push(T[w].l);
if(T[w].r!=) Q.push(T[w].r);
}
int len=v.size();
for(int i=;i<len;i++){
printf("%d%c",v[i],i==(len-)?'\n':' ');
}
} int main(){
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d",&po[i]);
for(int i=;i<n;i++) scanf("%d",&mid[i]);
int rt=mid_po_build(,n-,,n-);
dfs(rt);
return ;
}

最新文章

  1. tomcat启动的了,但是加载项目失败
  2. Linq查询表达式
  3. 怎么创建一个Database快照
  4. ASP.NET MVC学习之模型绑定(1)
  5. 图片--Android加载图片导致内存溢出(Out of Memory异常)
  6. epoll分析
  7. ASP.NET MVC 第五回 ActionResult的其它返回值
  8. [Android学习笔记]some tips
  9. VC中如何设置菜单项的触发状态?
  10. Visual Studio无法调试
  11. 使用docker部署SqlServer
  12. 获得驱动器信息卷设备&amp;&amp;Ring3得到磁盘文件系统(NTFS WIN10)
  13. 升级版updateOozie.sh
  14. CentOS 上开启 BBR 加速
  15. linux文件查看
  16. 端口扫描--zmap
  17. 写给在Java和.net中徘徊的新手
  18. Java中的Type
  19. C# 利用CMD命令行结束进程
  20. Java Class Object

热门文章

  1. input type=file的几个属性
  2. VMware Workstation14 安装Ubuntu18.04
  3. 身份认证功能chiro的使用
  4. day09(垃圾回收机制)
  5. C#导出Excel表格方法
  6. MySQL之字符集
  7. Hbuilder工具使用
  8. 解决使用Spring Boot、Multipartfile实现上传提示无法找到文件的问题
  9. Supervisor安装与使用
  10. VisualStudio神级插件Resharper技巧基础入门到骨灰玩家使用全教程+Resharper性能优化