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

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

初探Service服务发现机制

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

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...