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:后序和中序构造二叉树
后序和中序构造二叉树 题目输入格式输出格式输入样例(及其对应的二叉树) 代码 题目 本题目要求用后序序列和中序序列构造一棵二叉树(树中结点个数不超过10个),并输出其先序序列。 输入格式 在第一行中输入元素个数…...
二十三种设计模式全面解析-适配器模式的妙用:异构数据库和不同版本API的完美兼容!
在当今的软件开发领域,我们常常面对着与异构数据库和不同版本的API进行集成的挑战。这些系统和组件往往使用不同的数据结构和接口规范,导致我们的代码无法直接与它们进行交互。但是,不要担心!今天,我将向你揭示一个神奇…...
K7系列FPGA进行FLASH读写1——CCLK控制(STARTUPE2原语)
最近的工作涉及对 FPGA 进行远程更新,也就是通过远程通信接口将 .bin 文件送到 FPGA,然后写入 FLASH,这样当 FPGA 重新上电后就可以执行更新后的程序了。因此第一步工作就是进行 FLASH 的读写控制。 然而如果尝试配置 FLASH 管脚时࿰…...
【Kafka】基本概念
文章目录 一、消息队列的流派1.1 有Broker1.1.1 重topic1.1.2 轻topic 1.2 无Broker 二、kafka安装三、kafka基本术语四、发送消息五、消费消息六、单播消息七、多播消息八、查看消费组的详细信息九、主题topic十、分区十一、kafka中消息⽇志⽂件中保存的内容 一、消息队列的流…...
如何在Vue3项目中使用防抖节流技巧
前言 防抖节流是可以说是一种优化组件性能的技巧,可以有效减少组件中的渲染次数和计算量,从而提高组件的响应速度和用户体验。在Vue3中可以使用lodash库中的debounce和throttle函数来分别实现防抖和节流。当然也可以自行设计实现防抖节流函数࿰…...
快速排序(Java)
基本思想 快速排序Quicksort)是对冒泡排序的一种改进。 基本思想是分治的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排…...
在ffmpeg中,如何把h264转换为rgb格式
在ffmpeg中,网络视频流h264为什么默认的转为YUV而不是其他格式 文章中介绍了,h264解码的时候是直接解码为yuv的,如果在使用的过程中 需要用到rgb的格式,我们该如何来转换这种格式呢? 在上面的文章中,我们已…...
【重磅】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 什么是杂波? 1.2 杂波的频谱特性 二、动目标显示(MTI)技术 2.1 对消原理 2.2 数字对消器设计 三、MATLAB仿真 3.1 对消效果验证 3.2 代码 一、杂波及其特点 1.1 什么是杂波? 杂波是相对目标回波而言的,…...
Python-敲木鱼升级版(真手动版敲木鱼)
演示效果 需要安装的第三方库: pip install pygame # 加载音乐 pip install pillow # 加载图片 pip install mediapipe # 判断手势的模型 pip install opencv # 模型要用来处理图形 建议有独显和摄像头的可以尝试! 想着升级一下玩法,只有真敲…...
Websocket @ServerEndpoint不能注入@Autowired
在websocket中使用ServerEndpoint无法注入Autowired、Value 问题分析 Spring管理采用单例模式(singleton),而 WebSocket 是多对象的,即每个客户端对应后台的一个 WebSocket 对象,也可以理解成 new 了一个 WebSocket&…...
Unity热更新
1,热更新的概念与作用 app更新通常分为两类,一种是整包更新(换包),一种是热更新(不换包,通过网络下载,动态更新资源等)。 整包更新,是指在需要更新时&#x…...
如何用维格云搭建和一键训练你的钧瓷AI机器人?
大禹智库 第69期(总第400期) 2023年11月4日 如何用维格云搭建和一键训练你的钧瓷AI机器人? 钧瓷私有数据聊天机器人是一种能够根据预设的数据集进行智能对话的机器人。通过维格云,我们可以轻松地搭建自己的钧瓷私有数据聊天机器人。本文将以钧道机器人为例,详细介绍如何…...
整理的一些Java细节问题
1. 为什么要有无参构造? 在 Java 中,如果一个类没有显式定义构造方法,编译器会自动生成一个默认的无参构造方法(也称为默认构造方法)。无参构造方法是一个没有任何参数的构造方法。 无参构造方法的存在有几个重要原因…...
初识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 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 📕作者简介:热…...
dirhunt使用手册,中文版
“dirhunt” 的命令行工具的帮助信息,用于目录扫描和网站内容分析。以下是这个命令的使用方法和示例: 命令格式: dirhunt [OPTIONS] [URLS]… [URLS]…:一个或多个域名或 URL,可以加载来自文件的 URL,使用…...
【从0到1设计一个网关】如何设计一个稳定的网关?
文章目录 高可用分析软件架构心跳检测自动恢复熔断降级接口重试隔离压测和预案多机房灾备以及双活数据中心异常处理机制重试主备服务自动切换动态剔除或恢复异常机器超时时间的考虑服务设计这篇文章并没有具体的业务实现,而只是对于如何设计一个高可用,稳定的网关列举出了一些…...
chromedp库编写程序
步骤1:首先,我们需要导入chromedp库,以便使用它来下载网页内容。 import chromedp 步骤2:然后,我们需要创建一个函数,该函数接受一个URL作为参数,并使用chromedp库下载该URL的内容。 func do…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
