当前位置: 首页 > 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官网。 网卡配置 需要配…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...