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

L2-006 树的遍历

news 来源：原创 2025/8/14 17:20:15

L2-006 树的遍历

==问题描述==
==格式输入==
==格式输出==
==样例输入==
==样例输出==
==评测用例规模与约定==
==解析==
==参考程序==
难度等级

问题描述

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

格式输入

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

格式输出

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

样例输入

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

样例输出

4 1 6 3 5 7 2

评测用例规模与约定

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

解析

方法思路
重建二叉树：后序遍历的最后一个元素是根节点，在中序遍历中找到这个根节点，根节点左边的部分是左子树的中序遍历，右边是右子树的中序遍历。根据左子树的节点数目，可以在后序遍历中分割出左子树和右子树的后序遍历。递归处理左右子树即可重建二叉树。

层序遍历：使用队列进行广度优先搜索（BFS），依次访问每一层的节点，并按顺序输出。

参考程序

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {if (inStart > inEnd || postStart > postEnd) return nullptr;int rootVal = postorder[postEnd];TreeNode* root = new TreeNode(rootVal);int inRoot = inMap[rootVal];int numsLeft = inRoot - inStart;root->left = buildTree(inorder, postorder, inStart, inRoot - 1, postStart, postStart + numsLeft - 1, inMap);root->right = buildTree(inorder, postorder, inRoot + 1, inEnd, postStart + numsLeft, postEnd - 1, inMap);return root;
}
vector<int> levelOrder(TreeNode* root) {vector<int> result;if (!root) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();result.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}   return result;
}
int main() {int N;cin >> N;vector<int> postorder(N);vector<int> inorder(N);for (int i = 0; i < N; ++i) {cin >> postorder[i];}for (int i = 0; i < N; ++i) {cin >> inorder[i];}unordered_map<int, int> inMap;for (int i = 0; i < N; ++i) {inMap[inorder[i]] = i;}TreeNode* root = buildTree(inorder, postorder, 0, N - 1, 0, N - 1, inMap);vector<int> level = levelOrder(root);for (int i = 0; i < level.size(); ++i) {if (i != 0) cout << " ";cout << level[i];}cout << endl;return 0;
}

难度等级

⭐️⭐️⭐️（1~10星）

以个人刷题整理为目的，如若侵权，请联系删除~

L2-006 树的遍历

L2-006 树的遍历问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序难度等级问题描述给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。格式输入输入第一行给出一个正整数N&#xff0…...

编程日记 2025/8/14 17:20:15

在国产麒麟Kylin Linux Advanced Server V10中使用QT5开发环境并支持中文输入

切记：不要安装第三方源的工具包，包括QT官网的！！！ 在联网的情况下按以下步骤安装即可： sudo yum groupinstall "Development Tools" -y sudo yum install qt5-qtbase-devel qt5-qtdeclarative-d…...

编程日记 2025/8/11 6:51:39

C语言动规学习

文章目录一、动态规划的基本概念1. 最优子结构2. 重叠子问题二、动态规划的求解步骤三、动态规划与递归的比较四、例题（只讲思维，空间时间复杂度大小不与题目比较）1、斐波那契数列1. 定义状态2. 找出状态转移方程3. 初始化边界条件4. 确定计…...

编程日记 2025/8/11 8:32:51

Vue3中provide和inject的用法示例

在 Vue3 中，provide 和 inject 用于实现跨层级组件通信。以下是一个简单的示例： 1. 父组件 (祖先组件) - 提供数据 javascript 复制 // ParentComponent.vue import { provide, ref, reactive } from vue;export default {setup() {// 提供静态数据p…...

编程日记 2025/8/10 1:26:58

fastdds:传输层SHM和DATA-SHARING的区别

下图是fastdds官方的图，清晰地展示了dds支持的传输层: 根据通信双方的相对位置(跨机器、同机器跨进程、同进程)的不同选择合适的传输层，是通信中间件必须要考虑的事情。跨机器：udp、tcp 跨机器通信，只能通过网络， f…...

编程日记 2025/8/13 14:56:37

MQ基础篇

1.初识MQ 1.同步调用概念： 同步调用是一种程序执行方式，在调用一个函数或服务时，调用方会一直等待被调用方执行完成并返回结果，才会继续执行后续代码 ，期间调用线程处于阻塞状态。同步调用的优势： 时…...

编程日记 2025/8/13 15:25:16

网络编程2

day2 一、UDP编程 1.编程流程 2.函数接口 3.注意 (1)、对于TCP是先运行服务器，客户端才能运行。(2)、对于UDP来说，服务器和客户端运行顺序没有先后，因为是无连接，所以服务器和客户端谁先开始，没有关系.(3)、一个服务器…...

编程日记 2025/8/14 17:19:12

Python环境中在线训练机器学习模型所遇到的问题及解决方案

我最近开发个智能控制系统，包括实时数据采集、预测、策略优化等功能，最近增加在线学习功能，也就是在线进行模型训练，在线进行模型训练时出现了问题，现象为：控制台报： cmdstanpy - INFO - Chain [1] start processing所有任务、线程停止，Web服务登录无法访问后台的pyt…...

编程日记 2025/8/12 15:47:51

「仓颉编程语言」Demo

仓颉编程语言」Demo python 1)# 仓颉语言写字楼管理系统示例（虚构语法）# 语法规则：中文关键词类Python逻辑定义写字楼管理系统属性:租户库列表.新建()报修队列列表.新建()费用单价 5 # 元/平方米方法添加租户(名称, 楼层, 面积):…...

编程日记 2025/8/4 7:46:56

《软件设计师》复习笔记（11.4）——处理流程设计、系统设计、人机界面设计

目录一、业务流程建模二、流程设计工具三、业务流程重组（BPR） 四、业务流程管理（BPM） 真题示例： 五、系统设计 1. 主要目的 2. 设计方法 3. 主要内容 4. 设计原则真题示例： 六、人机界面设…...

编程日记 2025/8/8 11:27:03

win11系统截图的几种方式

在 Windows 11 中，系统内置的截图功能已全面升级，不仅支持多种截图模式，还整合了录屏、OCR 文字识别和 AI 增强编辑等功能。以下是从基础操作到高阶技巧的完整指南： 一、快捷键截图（效率首选） 1. Win Sh…...

编程日记 2025/8/14 17:19:13

http://noi.openjudge.cn/——2.5基本算法之搜索——1998:寻找Nemo

文章目录题目宽搜代码优先队列深搜代码小结题目总时间限制: 2000ms 内存限制: 65536kB 描述 Nemo 是个顽皮的小孩. 一天他一个人跑到深海里去玩. 可是他迷路了. 于是他向父亲 Marlin 发送了求救信号.通过查找地图 Marlin 发现那片海像一个有着墙和门的迷宫.所有的墙都是平行…...

编程日记 2025/8/11 13:49:54

win10系统完美配置mamba-ssm全整合方案

好久没瞎写东西了，刚好最近遇到一个逆天需求：要在win10平台上配置可用的mamba-ssm环境。由于这个环境原版以及相关依赖都是仅适配linux的，即使是依赖conda环境直接拿来往windows系统上装也全是bug，网上大量的垃圾教程也都是错的&a…...

编程日记 2025/8/11 21:24:54

MQTTClient.c中的协议解析与报文处理机制

MQTTClient.c中的协议解析与报文处理机制 1. 协议解析的核心逻辑 （1）报文头部解析 MQTT协议报文由固定头（Fixed Header） 可变头（Variable Header） 负载（Payload）三部分组成。在rea…...

编程日记 2025/8/4 7:48:17

LeetCode每日一题4.18

2364.统计坏数对的数目问题问题分析根据题目要求，(i, j) 是一个坏数对的条件是： i < j j - i ! nums[j] - nums[i]，即 nums[j] - j ! nums[i] - i 因此，我们可以转换问题：对于每个 j，找到所有 i &l…...

编程日记 2025/8/8 1:13:51

cmd查询占用端口并查杀

查看特定端口的占用情况 netstat -ano | findstr 端口号 netstat -ano | findstr 端口号结束指定进程 askkill /T /F /PID PID askkill /T /F /PID PID...

编程日记 2025/8/10 4:46:25

ETL数据集成平台在交通运输行业的五大应用场景

在智能交通与数字物流时代，交通运输企业每天产生海量数据——车辆轨迹、货物状态、乘客流量、设备日志……但这些数据往往被困在分散的系统中：GPS定位数据躺在车载终端里，物流订单卡在Excel表中，地铁客流统计锁在本地服务器内。如…...

编程日记 2025/8/10 10:34:52

自定义 el-menu

使用的工具：vue2 element-ui <!DOCTYPE html> <html><head><link rel"stylesheet" href"https://unpkg.com/element-ui/lib/theme-chalk/index.css"><style>.el-menu--horizontal {border-bottom: none !impor…...

编程日记 2025/8/1 12:33:59

创维E900V20C-国科GK6323V100C-rtl8822cs-安卓9.0-短接强刷卡刷固件包

创维E900V20C／创维E900V20D-国科GK6323V100C-安卓9.0-强刷卡刷固件包创维E900V20C 刷机说明： 1、用个老款4G，2.0的U盘，fat32，2048块单分区格式化， 5个文件复制到根目录，插盒子靠网口U口&…...

编程日记 2025/8/14 17:19:13

DemoGen：用于数据高效视觉运动策略学习的合成演示生成

25年2月来自清华、上海姚期智研究院和上海AI实验室的论文“DemoGen: Synthetic Demonstration Generation for Data-Efficient Visuomotor Policy Learning”。视觉运动策略在机器人操控中展现出巨大潜力，但通常需要大量人工采集的数据才能有效执行。驱动高数据需…...

编程日记 2025/8/14 17:19:12

影楼精修-高低频磨皮算法解析

注意：本文样例图片为了避免侵权，均使用AIGC生成； 高低频磨皮基础高低频磨皮是一种常用于人像后期修图的技术，它能在保留皮肤纹理的同时柔化瑕疵，使皮肤看起来更加自然细腻。高低频磨皮的算法原理如下： …...

编程日记 2025/8/14 11:09:25

打造搜索神功：Express 路由中的关键词探查之道

前言在 Web 开发的江湖，Express 好比一位身怀绝技的武林高手，出手稳准狠，擅长解决各种疑难杂症。今天，我们将与这位高手并肩作战，一探关键词搜索路由的奥义。这不是枯燥的教学，而是一场充满玄机与笑点的江湖奇遇。挥起代码之剑，踏上探索之路，不仅能习得招式，还能在轻…...

编程日记 2025/8/10 1:39:05

kubernetes-使用ceph-csi

kubernetes-使用ceph-csi Kubernetes （简称K8s）和Ceph都是开源的云计算技术，K8s是一个容器编排平台，而Ceph是一个分布式存储系统。将K8s和Ceph集成在一起可以为应用程序提供高可用性和持久性存储。本文主要介绍如何在使用openEul…...

编程日记 2025/8/3 17:15:05

从Shell到域控：内网渗透中定位域控制器的8种核心方法

在内网渗透中，定位域控制器（Domain Controller, DC）是攻防对抗的关键环节。本文结合实战经验与工具技术，总结出8种从Shell快速发现域控主机的方法，涵盖命令探测、网络扫描、日志分析等维度，助你系统…...

编程日记 2025/8/14 12:35:35

FA-YOLO：基于FMDS与AGMF的高效目标检测算法解析

本文《FA-YOLO: Research On Efficient Feature Selection YOLO Improved Algorithm Based On FMDS and AGMF Modules》针对YOLO系列在特征融合与动态调整上的不足，提出两种创新模块：FMDS（细粒度多尺度动态选择模块）和AGMF（自适应门控多分支聚焦融合模块）。论文结构…...

编程日记 2025/8/8 13:41:52

【RK3588 嵌入式图形编程】-SDL2-扫雷游戏-结束和重新开始游戏

结束和重新开始游戏文章目录结束和重新开始游戏1、概述2、更新Globals.h3、触发GAME_WON和GAME_LOST事件4、对游戏结束的反应5、重启游戏6、创建新游戏按钮7、完整代码8、总结在本文中，将实现胜负检测并添加重新开始功能以完成游戏循环。 1、概述在本文中，我们将更新我们…...

编程日记 2025/8/10 1:39:05

OpenAI重返巅峰：o3与o4-mini引领AI推理新时代

引言 2025年4月16日，OpenAI发布了全新的o系列推理模型：o3和o4-mini，这两款模型被官方称为“迎今为止最智能、最强大的大语言模型（LLM）”。它们不仅在AI推理能力上实现了质的飞跃，更首次具备了全面的工具使…...

编程日记 2025/8/9 5:29:53

《软件设计师》复习笔记（12.3）——质量管理、风险管理

目录一、质量管理 1. 质量定义 2. 质量管理过程 3. 软件质量特性（GB/T 16260-2002） 4. 补充知识 McCall质量模型： 软件评审软件容错技术真题示例： 二、风险管理 1. 风险管理的目的： 2. 风险管理流程及内…...

编程日记 2025/8/7 5:58:11

优化自旋锁的实现

在《C11实现一个自旋锁》介绍了分别使用TAS和CAS算法实现自旋锁的方案，以及它们的优缺点。TAS算法虽然实现简单，但是因为每次自旋时都要导致一场内存总线流量风暴，对全局系统影响很大，一般都要对它进行优化，以降低对全…...

编程日记 2025/8/10 15:04:44

从antd中拿一个表格表格 Table - Ant Designhttps://ant-design.antgroup.com/components/table-cn#table-demo-edit-cell使用的是可编辑单元格实现引入可编辑单元格： import React, { useState, useEffect, useRef, useContext } from react import { Button, …...

编程日记 2025/8/13 20:39:46

人像面部关键点检测

此工作为本人近期做人脸情绪识别，CBAM模块前是否能加人脸关键点检测而做的尝试。由于创新点不是在于检测点的标注，而是CBAM的改进，因此，只是借用了现成库Dilb与cv2进行。首先，下载人脸关键点预测模型:Index of /file…...

编程日记 2025/8/12 5:11:10

OpenVINO怎么用

目录 OpenVINO 简介主要组件安装 OpenVINO 使用 OpenVINO 的基本步骤 OpenVINO 简介 OpenVINO（Open Visual Inference and Neural Network Optimization）是英特尔推出的一个开源工具包，旨在帮助开发者在英特尔硬件平台上高效部署深度学…...

编程日记 2025/8/9 8:40:53

写论文时降AIGC和降重的一些注意事项

‘ 写一些研究成果，英文不是很好，用有道翻译过来句子很简单，句型很单一。那么你会考虑用ai吗？ 如果语句太正式，高级，会被误判成aigc ，慎重选择ai润色。有的话就算没有用ai生成，但…...

编程日记 2025/8/14 1:04:38

SpringBoot学习（properties、yml(主流)、yaml格式配置文件）(读取yml配置文件的3种方式)(详解)

目录一、SpringBoot配置文件详解。 1.1配置文件简介。 1.2配置文件分类。（3种配置文件格式） <1>application.properties（properties格式）。 <2>application.yml（yml格式）。 <3>applicat…...

编程日记 2025/8/11 3:11:52

STM32单片机C语言

1、stdint.h简介 stdint.h 是从 C99 中引进的一个标准 C 库的文件路径：D:\MDK5.34\ARM\ARMCC\include 大家都统一使用一样的标准，这样方便移植配置MDK支持C99 位操作如何给寄存器某个值赋值举个例子：uint32_t temp 0; 宏定义带参…...

编程日记 2025/8/7 22:49:51

前端为什么需要单元测试？

一. 前言对于现在的前端工程，一个标准完整的项目，通常情况单元测试是非常必要的。但很多时候我们只是完成了项目而忽略了项目测试。我认为其中一个很大的原因是很多人对单元测试认知不够，因此我写了这篇文章，一方面期望通过这篇…...

编程日记 2025/8/7 1:54:27

QT 文件和文件夹操作

文件操作 1. 文件读写 QFile - 基本文件操作 // 只写模式创建文件（如果文件已存在会清空内容） file.open(QIODevice::WriteOnly);// 读写模式创建文件 file.open(QIODevice::ReadWrite);// 追加模式（如果文件不存在则创建） fil…...

编程日记 2025/8/11 4:31:16

AIP目录

专注于开发灵活API的设计文档。 AIP是总结了谷歌API设计决策的设计文档，它也为其他人提供了用文档记录API设计规则和实践的框架和系统。基础1AIP目的和指南2AIP编号规则3AIP版本管理200先例8AIP风格与指导9术语表流程100API设计评审常见问题205Beta版本发布前置条…...

编程日记 2025/8/12 8:39:47

Function Calling的时序图（含示例）

🧍 用户： 发起请求，输入 prompt（比如：“请告诉我北京的天气”）。 🟪 应用： 将用户输入的 prompt 和函数定义（包括函数名、参数结构等）一起发给 OpenAI。 …...

编程日记 2025/8/6 23:36:39

基于尚硅谷FreeRTOS视频笔记——6—滴答时钟—上下文切换

FreeRTOS滴答 FreeRTOS需要有一个时钟参照，并且这个时钟不会被轻易打断，所以最好选择systick 为什么需要时间参照就是在高优先级任务进入阻塞态后，也可以理解为进入delay（）函数后，需要有一个时间参照&…...

编程日记 2025/8/9 1:30:20

Playwright框架入门

Playwright爬虫框架入门 Playwright介绍 playwright官方文档 Playwright是一个用于自动化浏览器操作的开源工具，由Microsoft开发和维护，支持多种浏览器和多种编程语言，可以用于测试、爬虫、自动化任务等场景。 Playwright是基于WebSocket…...

编程日记 2025/8/13 8:58:27

针对渲染圆柱体出现“麻花“状问题解决

圆柱体渲染结果，在侧面有麻花状条纹，边缘不够硬朗，上下的圆看起来不够平，很明显，是法向量导致的。原始模型渲染结果计算点的法向量采用简单的平均法&#xf…...

编程日记 2025/8/13 16:11:30

手撕数据结构算法OJ——栈和队列

文章目录一、前言二、手撕OJ2.1有效的括号2.2用队列实现栈2.2.1初始化2.2.2入栈2.2.3出栈2.2.4取栈顶2.2.5判空2.2.6销毁2.2.7整体代码 2.3用栈实现队列2.3.1初始化2.3.2入队2.3.3出队2.3.4取队头2.3.5判空2.3.6销毁2.3.7整体代码四、总结一、前言兄弟们，今天的…...

编程日记 2025/8/9 7:36:40

基础知识-指针

1、指针的基本概念 1.1 什么是指针 1.1.1 指针的定义指针是一种特殊的变量，与普通变量存储具体数据不同，它存储的是内存地址。在计算机程序运行时，数据都被存放在内存中，而指针就像是指向这些数据存放位置的 “路标”。通过指针…...

编程日记 2025/8/14 0:01:32

Thymeleaf简介

在Java中，模板引擎可以帮助生成文本输出。常见的模板引擎包括FreeMarker、Velocity和Thymeleaf等 Thymeleaf是一个适用于Web和独立环境的现代服务器端Java模板引擎。 Thymeleaf 和 JSP比较： Thymeleaf目前所作的工作和JSP有相似之处，Thyme…...

编程日记 2025/8/9 4:51:43