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

PAT甲级-1020 Tree Traversals

题目

题目大意

给出一棵树的后序遍历和中序遍历,要求输出该树的层序遍历。

思路

非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构,用递归锁定根节点,然后再遍历左右子树,我之前发过类似题目的博客,这里就不再详细赘述。层序遍历就是使用队列了。

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int n;
vector<int> hou, mid, level;
struct node{int data;node * lchild, *rchild;
};void buildtree(node * &root, int hl, int hr, int ml, int mr){if (hl > hr || ml > mr){return;}int pos;for (int i = ml; i <= mr; i++){if (hou[hr] == mid[i]){pos = i;break;}}root = new node();root->data = hou[hr];root->lchild = root->rchild = nullptr;buildtree(root->lchild, hl, hl + pos - ml - 1, ml, pos - 1);buildtree(root->rchild, hl + pos - ml, hr - 1, pos + 1, mr);
}void findlevel(node * root){queue<node *> q;q.push(root);while (!q.empty()){node * now = q.front();level.push_back(now->data);q.pop();if (now->lchild) q.push(now->lchild);if (now->rchild) q.push(now->rchild);}
}int main(){cin >> n;hou.resize(n);mid.resize(n);for (int i = 0; i < n; i++){cin >> hou[i];}for (int i = 0; i < n; i++){cin >> mid[i];}node * root = nullptr;buildtree(root, 0, n - 1, 0, n - 1);findlevel(root);for (int i = 0; i < (int)level.size(); i++){if (i != 0) cout << " ";cout << level[i];}cout << endl;return 0;
}

相关文章:

PAT甲级-1020 Tree Traversals

题目 题目大意 给出一棵树的后序遍历和中序遍历&#xff0c;要求输出该树的层序遍历。 思路 非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构&#xff0c;用递归锁定根节点&#xff0c;然后再遍历左右子树&#xff0c;我之前发过类似题目的博客&…...

LVGL+FreeRTOS实战项目:智能健康助手(Max30102篇)

MAX30102 心率血氧模块简介 功能&#xff1a;用于检测心率和血氧饱和度&#xff0c;集成了红外和红光 LED 以及光电二极管。 接口&#xff1a;支持 I2C 通信&#xff0c;默认 I2C 地址为 0x57。 应用&#xff1a;广泛用于健康监测设备中&#xff0c;如智能手环、手表等。 硬…...

人脸识别【python-基于OpenCV】

1. 导入并显示图片 #导入模块 import cv2 as cv#读取图片 imgcv.imread(img/wx(1).jpg) #路径名为全英文&#xff0c;出现中文 图片加载失败,"D:\picture\wx.jpg" #显示图片 &#xff08;显示标题&#xff0c;显示图片对象&#xff09; cv.imshow(read_picture,im…...

redis常用命令和内部编码

文章目录 redis 为什么快redis中的Stringsetsetnxsetex getmsetmget计数操作incr、incrby、decr、decrby、incrbyfloatincrincrbyincrbyfloat 拼接&#xff08;append&#xff09;、获取(getrange)、修改字符串(setrange)、获取字符串长度(strlen)操作appendgetrangesetrangest…...

UI操作总结

该类 SolarWebx 继承自 Webx 和 IUixLikeMixin&#xff0c;主要用于扩展 giraffe.EasyUILibrary 的功能&#xff0c;提供了一系列与网页操作、元素定位、截图、图片处理等相关的方法。以下是对该类中每个方法的简要总结&#xff1a; __init__ 方法 作用&#xff1a;初始化 Sola…...

数据结构——实验八·学生管理系统

嗨~~欢迎来到Tubishu的博客&#x1f338;如果你也是一名在校大学生&#xff0c;正在寻找各种编程资源&#xff0c;那么你就来对地方啦&#x1f31f; Tubishu是一名计算机本科生&#xff0c;会不定期整理和分享学习中的优质资源&#xff0c;希望能为你的编程之路添砖加瓦⭐&…...

力扣hot100-->滑动窗口、贪心

你好呀&#xff0c;欢迎来到 Dong雨 的技术小栈 &#x1f331; 在这里&#xff0c;我们一同探索代码的奥秘&#xff0c;感受技术的魅力 ✨。 &#x1f449; 我的小世界&#xff1a;Dong雨 &#x1f4cc; 分享我的学习旅程 &#x1f6e0;️ 提供贴心的实用工具 &#x1f4a1; 记…...

Linux 内核中的高效并发处理:深入理解 hlist_add_head_rcu 与 NAPI 接口

在 Linux 内核的开发中,高效处理并发任务和数据结构的管理是提升系统性能的关键。特别是在网络子系统中,处理大量数据包的任务对性能和并发性提出了极高的要求。本文将深入探讨 Linux 内核中的 hlist_add_head_rcu 函数及其在 NAPI(网络接收处理接口)中的应用,揭示这些机制…...

centos哪个版本建站好?centos最稳定好用的版本

在信息化飞速发展的今天&#xff0c;服务器操作系统作为构建网络架构的基石&#xff0c;其稳定性和易用性成为企业和个人用户关注的重点。CentOS作为一款广受欢迎的开源服务器操作系统&#xff0c;凭借其强大的性能、出色的稳定性和丰富的软件包资源&#xff0c;成为众多用户建…...

软件越跑越慢的原因分析

如果是qt软件&#xff0c;可以用Qt Creator Profiler 作性能监控如果是通过web请求&#xff0c;可以用JMeter监控。 软件运行过程中逐渐变慢的现象&#xff0c;通常是因为系统资源&#xff08;如 CPU、内存、磁盘 I/O 等&#xff09;逐渐被消耗或软件中存在性能瓶颈。这个问题…...

LeetCode 力扣热题100 二叉树的直径

class Solution { public:// 定义一个变量 maxd&#xff0c;用于存储当前二叉树的最大直径。int maxd 0; // 主函数&#xff0c;计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 maxDepth 函数进行递归计算&#xff0c;并更新 maxd。maxDepth(root);// …...

【图文详解】lnmp架构搭建Discuz论坛

安装部署LNMP 系统及软件版本信息 软件名称版本nginx1.24.0mysql5.7.41php5.6.27安装nginx 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客: 关闭防火墙 systemctl stop firewalld &&a…...

小哆啦解题记:整数转罗马数字

小哆啦解题记&#xff1a;整数转罗马数字 小哆啦开始力扣每日一题的第十四天 https://leetcode.cn/problems/integer-to-roman/submissions/595220508/ 第一章&#xff1a;神秘的任务 一天&#xff0c;哆啦A梦接到了一项任务——将一个整数转换为罗马数字。他心想&#xff1a;…...

【Java数据结构】排序

【Java数据结构】排序 一、排序1.1 排序的概念1.2 排序的稳定性1.3 内部排序和外部排序1.3.1 内部排序1.3.2 外部排序 二、插入排序2.1 直接插入排序2.2 希尔排序 三、选择排序3.1 选择排序3.2 堆排序 四、交换排序4.1 冒泡排序4.2 快速排序Hoare法&#xff1a;挖坑法&#xff…...

我的求职之路合集

我把我秋招和春招的一些笔面试经验在这里发一下&#xff0c;网友们也可以参考一下。 我的求职之路&#xff1a;&#xff08;1&#xff09;如何谈自己的缺点 我的求职之路&#xff1a;&#xff08;2&#xff09;找工作时看重的点 我的求职之路&#xff1a;&#xff08;3&…...

数据结构(四) B树/跳表

目录 1. LRU 2. B树 3. 跳表 1. LRU: 1.1 概念: 最近最少使用算法, 就是cache缓存的算法. 因为cache(位于内存和cpu之间的存储设备)是一种容量有限的缓存, 有新的数据进入就需要将原本的数据进行排出. 1.2 LRU cache实现: #include <iostream> #include <list>…...

Arcgis国产化替代:Bigemap Pro正式发布

在数字化时代&#xff0c;数据如同新时代的石油&#xff0c;蕴含着巨大的价值。从商业决策到科研探索&#xff0c;从城市规划到环境监测&#xff0c;海量数据的高效处理、精准分析与直观可视化&#xff0c;已成为各行业突破发展瓶颈、实现转型升级的关键所在。历经十年精心打磨…...

LBS 开发微课堂|AI向导接口服务:重塑用户的出行体验

为了让广大开发者 更深入地了解 百度地图开放平台的 技术能力 轻松掌握满满的 技术干货 更加简单地接入 位置服务 我们特别推出了 “位置服务&#xff08;LBS&#xff09;开发微课堂” 系列技术案例 第六期的主题是 《AI向导接口服务的能力与接入方案》 随着地图应…...

AI导航工具我开源了利用node爬取了几百条数据

序言 别因今天的懒惰&#xff0c;让明天的您后悔。输出文章的本意并不是为了得到赞美&#xff0c;而是为了让自己能够学会总结思考&#xff1b;当然&#xff0c;如果有幸能够给到你一点点灵感或者思考&#xff0c;那么我这篇文章的意义将无限放大。 背景 随着AI的发展市面上…...

openstack单机安装

openstack单机安装 网卡配置安装依赖开启虚拟环境修改配置文件 部署openstack部署openstack客户端访问可视化界面Horizon补充 本篇主要讲述Ubuntu2204单机安装openstackstable/2024.2。其他版本的Linux系统或者openstack版本&#xff0c;请参考openstack官网。 网卡配置 需要配…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...