当前位置: 首页 > news >正文

PTA:后序和中序构造二叉树

后序和中序构造二叉树

  • 题目
    • 输入格式
    • 输出格式
    • 输入样例(及其对应的二叉树)
  • 代码

题目

本题目要求用后序序列和中序序列构造一棵二叉树(树中结点个数不超过10个),并输出其先序序列。

输入格式

在第一行中输入元素个数。

第二行中输入后序序列,用空格分隔。

第三行中输入中序序列,用空格分隔。

输出格式

输出此二叉树的先序序列,用空格分隔,最后也有一个空格。

输入样例(及其对应的二叉树)

5
20 40 50 30 10
20 10 40 30 50
## 输出样例
10 20 30 40 50 

代码

#include <iostream>
#include <vector>
#include <unordered_map>class TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, std::unordered_map<int, int>& indexMap) {if (inStart > inEnd || postStart > postEnd) {return nullptr;}int rootVal = postorder[postEnd];TreeNode* root = new TreeNode(rootVal);int rootIndex = indexMap[rootVal];int leftSubtreeSize = rootIndex - inStart;root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSubtreeSize - 1, indexMap);root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSubtreeSize, postEnd - 1, indexMap);return root;
}void preorderTraversal(TreeNode* root) {if (root == nullptr) {return;}std::cout << root->val << " ";preorderTraversal(root->left);preorderTraversal(root->right);
}int main() {int n;std::cin >> n;std::vector<int> postorder(n);std::vector<int> inorder(n);for (int i = 0; i < n; ++i) {std::cin >> postorder[i];}for (int i = 0; i < n; ++i) {std::cin >> inorder[i];}std::unordered_map<int, int> indexMap;for (int i = 0; i < n; ++i) {indexMap[inorder[i]] = i;}TreeNode* root = buildTree(inorder, postorder, 0, n - 1, 0, n - 1, indexMap);preorderTraversal(root);std::cout << std::endl;return 0;
}

相关文章:

PTA:后序和中序构造二叉树

后序和中序构造二叉树 题目输入格式输出格式输入样例&#xff08;及其对应的二叉树&#xff09; 代码 题目 本题目要求用后序序列和中序序列构造一棵二叉树&#xff08;树中结点个数不超过10个&#xff09;&#xff0c;并输出其先序序列。 输入格式 在第一行中输入元素个数…...

二十三种设计模式全面解析-适配器模式的妙用:异构数据库和不同版本API的完美兼容!

在当今的软件开发领域&#xff0c;我们常常面对着与异构数据库和不同版本的API进行集成的挑战。这些系统和组件往往使用不同的数据结构和接口规范&#xff0c;导致我们的代码无法直接与它们进行交互。但是&#xff0c;不要担心&#xff01;今天&#xff0c;我将向你揭示一个神奇…...

K7系列FPGA进行FLASH读写1——CCLK控制(STARTUPE2原语)

最近的工作涉及对 FPGA 进行远程更新&#xff0c;也就是通过远程通信接口将 .bin 文件送到 FPGA&#xff0c;然后写入 FLASH&#xff0c;这样当 FPGA 重新上电后就可以执行更新后的程序了。因此第一步工作就是进行 FLASH 的读写控制。 然而如果尝试配置 FLASH 管脚时&#xff0…...

【Kafka】基本概念

文章目录 一、消息队列的流派1.1 有Broker1.1.1 重topic1.1.2 轻topic 1.2 无Broker 二、kafka安装三、kafka基本术语四、发送消息五、消费消息六、单播消息七、多播消息八、查看消费组的详细信息九、主题topic十、分区十一、kafka中消息⽇志⽂件中保存的内容 一、消息队列的流…...

如何在Vue3项目中使用防抖节流技巧

前言 防抖节流是可以说是一种优化组件性能的技巧&#xff0c;可以有效减少组件中的渲染次数和计算量&#xff0c;从而提高组件的响应速度和用户体验。在Vue3中可以使用lodash库中的debounce和throttle函数来分别实现防抖和节流。当然也可以自行设计实现防抖节流函数&#xff0…...

快速排序(Java)

基本思想 快速排序Quicksort&#xff09;是对冒泡排序的一种改进。 基本思想是分治的思想&#xff1a;通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分数据分别进行快速排…...

在ffmpeg中,如何把h264转换为rgb格式

在ffmpeg中&#xff0c;网络视频流h264为什么默认的转为YUV而不是其他格式 文章中介绍了&#xff0c;h264解码的时候是直接解码为yuv的&#xff0c;如果在使用的过程中 需要用到rgb的格式&#xff0c;我们该如何来转换这种格式呢&#xff1f; 在上面的文章中&#xff0c;我们已…...

【重磅】Cookies、headers、Session规律总结,搞定卡点

【重磅】Cookies规律总结,搞定卡点 登录后开始正式获取数据阶段: 不使用session: 放在请求头headers中 当如是:headers = {“user-agent”: “Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36”,“Coo…...

【雷达原理】雷达杂波抑制方法

目录 一、杂波及其特点 1.1 什么是杂波&#xff1f; 1.2 杂波的频谱特性 二、动目标显示(MTI)技术 2.1 对消原理 2.2 数字对消器设计 三、MATLAB仿真 3.1 对消效果验证 3.2 代码 一、杂波及其特点 1.1 什么是杂波&#xff1f; 杂波是相对目标回波而言的&#xff0c;…...

Python-敲木鱼升级版(真手动版敲木鱼)

演示效果 需要安装的第三方库&#xff1a; pip install pygame # 加载音乐 pip install pillow # 加载图片 pip install mediapipe # 判断手势的模型 pip install opencv # 模型要用来处理图形 建议有独显和摄像头的可以尝试&#xff01; 想着升级一下玩法&#xff0c;只有真敲…...

Websocket @ServerEndpoint不能注入@Autowired

在websocket中使用ServerEndpoint无法注入Autowired、Value 问题分析 Spring管理采用单例模式&#xff08;singleton&#xff09;&#xff0c;而 WebSocket 是多对象的&#xff0c;即每个客户端对应后台的一个 WebSocket 对象&#xff0c;也可以理解成 new 了一个 WebSocket&…...

Unity热更新

1&#xff0c;热更新的概念与作用 app更新通常分为两类&#xff0c;一种是整包更新&#xff08;换包&#xff09;&#xff0c;一种是热更新&#xff08;不换包&#xff0c;通过网络下载&#xff0c;动态更新资源等&#xff09;。 整包更新&#xff0c;是指在需要更新时&#x…...

如何用维格云搭建和一键训练你的钧瓷AI机器人?

大禹智库 第69期(总第400期) 2023年11月4日 如何用维格云搭建和一键训练你的钧瓷AI机器人? 钧瓷私有数据聊天机器人是一种能够根据预设的数据集进行智能对话的机器人。通过维格云,我们可以轻松地搭建自己的钧瓷私有数据聊天机器人。本文将以钧道机器人为例,详细介绍如何…...

整理的一些Java细节问题

1. 为什么要有无参构造&#xff1f; 在 Java 中&#xff0c;如果一个类没有显式定义构造方法&#xff0c;编译器会自动生成一个默认的无参构造方法&#xff08;也称为默认构造方法&#xff09;。无参构造方法是一个没有任何参数的构造方法。 无参构造方法的存在有几个重要原因…...

初识AUTOSAR网络管理

文章目录 目的模式时间参数T_REPEAT_MESSAGET_NM_TIMEOUTT_WAIT_BUS_SLEEPT_START_Tx_AppFrameT_NM_ImmediateCycleTimeT_NM_MessageCycleN_ImmediateNM_TIMEST_START_NM_TXT_WakeUp跳转状态NM_1NM_2NM_3NM_4NM_5NM_6NM_7...

Flink SQL Hive Connector使用场景

目录 1.介绍 2.使用 2.1注册HiveCatalog 2.2Hive Read 2.2.1流读关键配置 2.2.2示例...

【Docker】联合探讨Docker:容器化技术的革命性应用

前言 Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 &#x1f4d5;作者简介&#xff1a;热…...

dirhunt使用手册,中文版

“dirhunt” 的命令行工具的帮助信息&#xff0c;用于目录扫描和网站内容分析。以下是这个命令的使用方法和示例&#xff1a; 命令格式&#xff1a; dirhunt [OPTIONS] [URLS]… [URLS]…&#xff1a;一个或多个域名或 URL&#xff0c;可以加载来自文件的 URL&#xff0c;使用…...

【从0到1设计一个网关】如何设计一个稳定的网关?

文章目录 高可用分析软件架构心跳检测自动恢复熔断降级接口重试隔离压测和预案多机房灾备以及双活数据中心异常处理机制重试主备服务自动切换动态剔除或恢复异常机器超时时间的考虑服务设计这篇文章并没有具体的业务实现,而只是对于如何设计一个高可用,稳定的网关列举出了一些…...

chromedp库编写程序

步骤1&#xff1a;首先&#xff0c;我们需要导入chromedp库&#xff0c;以便使用它来下载网页内容。 import chromedp 步骤2&#xff1a;然后&#xff0c;我们需要创建一个函数&#xff0c;该函数接受一个URL作为参数&#xff0c;并使用chromedp库下载该URL的内容。 func do…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...