二叉树遍历C++

news/2024/11/23 3:21:18/

假设二叉树上各结点的权值互不相同且都为正整数。
给定二叉树的后序遍历和中序遍历,请你输出二叉树的前序遍历的最后一个数字。

输入格式
第一行包含整数 N,表示二叉树结点总数。
第二行给出二叉树的后序遍历序列。
第三行给出二叉树的中序遍历序列。

输出格式
输出二叉树的前序遍历的最后一个数字。

数据范围
1≤N≤50000,
二叉树结点权值范围 [1,109]。

输入样例:
7
1 2 3 4 5 6 7
2 1 4 3 7 5 6

输出样例:
5

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=50010;
int a[N],b[N],res,n;
unordered_map<int,int> p;
void build(int al,int ar,int bl,int br)
{if(al>ar) return;int root=a[ar];int k=p[root];res=root;build(al,al+k-bl-1,bl,k-1);build(al+k-bl,ar-1,k+1,br);
}
int main()
{cin>>n;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++){cin>>b[i];p[b[i]]=i;}build(0,n-1,0,n-1);cout<<res;return 0;
}

http://www.ppmy.cn/news/1302398.html

相关文章

150套简约流行国内外优秀网页模板打包 /个人主页网站html模板 /html+css网页设计源码(分享)

这里把自己收藏的最新150套简约流行国内外优秀网页模板打包分享给大家&#xff0c;如果有用请点赞收藏&#xff0c;无密源码&#xff0c;直接拿来就可以用的。它是htmlcss网页设计源码&#xff0c;html5网页静态模板。 我分了品类&#xff0c;按行业或应用场景&#xff0c;不但…

在vue3和上挂载方法,以及在页面中怎么使用原型(公共)上的方法

//新建的项目的main.js文件是这样的 //main.js 文件 //befor import { createApp } from vue; import App from ./App.vue;const app createApp(App); app.mount(#app);以下例子用于解释在vue3.0的main.js中挂载公共的方法&#xff08;foo&#xff09; //main.js 文件 //afte…

PingCAP 受邀参加 FICC 2023,获 Open100 世纪全球开源贡献奖

2023 年 12 月&#xff0c;2023 国际测试委员会智能计算与芯片联邦大会&#xff08;FICC 2023&#xff09;在海南三亚举办&#xff0c;中外院士和数十位领域专家莅临出席。 大会现场 &#xff0c;开放源代码促进会创始人 Bruce Perens 颁发了 Open100 世纪全球开源贡献奖&…

vue3的福音框架arco.design

前言&#xff1a; 在vue2于2023年底正式宣布不在维护&#xff0c;vue3使用越来越频繁的时刻&#xff0c;我们实现项目的辅助框架也越来越多。element, iview, antd 等经典框架继续风靡一时&#xff0c;不过也有很多好的框架&#xff0c;功能也强大&#xff0c;比如我们今天说的…

VMware workstation安装debian-12.1.0虚拟机并配置网络

VMware workstation安装debian-12.1.0虚拟机并配置网络 Debian 是一个完全自由的操作系统&#xff01;Debian 有一个由普罗大众组成的社区&#xff01;该文档适用于在VMware workstation平台安装debian-12.1.0虚拟机。 1.安装准备 1.1安装平台 Windows 11 1.2软件信息 软…

Pytest测试 —— 如何使用属性来标记测试函数!

在软件开发领域&#xff0c;单元测试是确保代码质量和可维护性的关键一环。随着项目的不断发展&#xff0c;测试用例的管理变得愈发复杂&#xff0c;而一些测试可能需要特殊的处理、环境或者标记。在Python中&#xff0c;我们可以通过使用属性&#xff08;Attribute&#xff09…

数据结构第十三弹---链式二叉树基本操作(上)

链式二叉树 1、结构定义2、手动创建二叉树3、前序遍历4、中序遍历5、后序遍历6、层序遍历7、计算结点个数8、计算叶子结点个数9、计算第K层结点个数10、计算树的最大深度总结 1、结构定义 实现一个数据结构少不了数据的定义&#xff0c;所以第一步需要定义二叉树的机构。 typ…

计算机毕业设计----SSH电子相册管理系统

项目介绍 本项目分为普通用户与管理员两个角色&#xff1b; 管理员角色包含以下功能&#xff1a; 管理员登陆,用户信息管理,登陆密码修改等功能。 用户角色包含以下功能&#xff1a; 用户登陆,个人信息管理,相册管理,上传照片等功能。 环境需要 1.运行环境&#xff1a;最好…