AcWing 1550:完全二叉搜索树
【题目来源】
https://www.acwing.com/problem/content/1552/
【题目描述】
二叉搜索树 (BST) 递归定义为具有以下属性的二叉树:
(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
(2)若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值
(3)它的左、右子树也分别为二叉搜索树
完全二叉树 (CBT) 定义为除最深层外的其他层的结点数都达到最大个数,最深层的所有结点都连续集中在最左边的二叉树。
现在,给定 N 个不同非负整数,表示 N 个结点的权值,用这 N 个结点可以构成唯一的完全二叉搜索树。
请你输出该完全二叉搜索树的层序遍历。
【输入格式】
第一行包含整数 N,表示结点个数。
第二行包含 N 个不同非负整数,表示每个结点的权值。
【输出格式】
共一行,输出给定完全二叉搜索树的层序遍历序列。
【数据范围】
1≤N≤1000,
结点权值不超过 2000。
【输入样例】
10
1 2 3 4 5 6 7 8 9 0
【输出样例】
6 3 8 1 5 7 9 0 2 4
【算法分析】
● 二叉搜索树(BST,Binary Search Tree)
二叉搜索树的形态与给定的序列值及顺序相关。也就是说,即便序列的值相同,但依据“左小右大”的原则,不同的次序也会生成不同形态的二叉搜索树。

(45,24,53,12,37,93) (12,24,37,45,53,93)
● 完全二叉树
如果在一棵具有n个结点的二叉树中,它的逻辑结构与满二叉树的前n个结点的逻辑结构相同,则称这样的二叉树为完全二叉树。显然,在完全二叉树中,结点 u 的左孩子为 2*u,右孩子为 2*u+1。

● 二叉搜索树具有一个重要的性质,即它的中序遍历序列是递增的。那又如何据此性质,输出二叉搜索树的层序遍历序列呢?
对二叉搜索树的结点值进行递增排序,然后执行类似于中序遍历的 dfs 操作,并在 dfs 过程中将对应的二叉搜索树结点值存入一个中序数组中,之后输出中序数组便可得到所求的二叉搜索树的层序遍历序列。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=1010;
int a[maxn],in[maxn];
int n,idx;void dfs(int u) { //inorderif(u*2<=n) dfs(u*2);in[u]=a[idx++];if(u*2+1<=n) dfs(u*2+1);
}int main() {cin>>n;for(int i=0; i<n; i++) cin>>a[i];sort(a,a+n);dfs(1); //is 1,not 0. Otherwise,dfs can't run.for(int i=1; i<=n; i++) cout<<in[i]<<" ";return 0;
}/*
in:
10
1 2 3 4 5 6 7 8 9 0out:
6 3 8 1 5 7 9 0 2 4
*/
【参考文献】
https://blog.csdn.net/justinzengTM/article/details/81459482
https://www.acwing.com/solution/content/11649/
https://www.acwing.com/solution/content/97469/
相关文章:
AcWing 1550:完全二叉搜索树
【题目来源】https://www.acwing.com/problem/content/1552/【题目描述】二叉搜索树 (BST) 递归定义为具有以下属性的二叉树: (1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 (2)若它的右…...
使用kali Linux启动盘轻松破解Windows电脑密码
破解分析文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。谢谢!! 效果展示: 使用kali Linux可以轻松破解Windows用户及密码 准备阶段: (…...
Vue2中跨组件共享公共属性的方法、优缺点与实现
一、vuex(最常用) 优缺点 优点:集中管理状态,组件间解耦,易于调试和测试。缺点:学习成本较高,对于小项目可能过于复杂。 适用场景 大型、复杂的单页面应用(SPA)。需要全局…...
2024亚太杯数学建模竞赛(B题)的全面解析
你是否在寻找数学建模比赛的突破点?数学建模进阶思路! 作为经验丰富的数学建模团队,我们将为你带来2024亚太杯数学建模竞赛(B题)的全面解析。这个解决方案包不仅包括完整的代码实现,还有详尽的建模过程和解…...
【PWN · ret2syscall | GoPwn】[2024CISCN · 华中赛区]go_note
一道GoPwn,此外便是ret2syscall的利用。然而过程有不小的曲折,参考 返璞归真 师傅的wp,堪堪完成了复现。复现过程中,师傅也灰常热情回答我菜菜的疑问,感谢!2024全国大学生信息安全竞赛(ciscn&am…...
关于学习方法的优化
这是一种新的学习方法,一种新的学习形式,可以通过歌唱的方式,运用,把自己每天要进行的内容进行一个复习,进行一个重复,这样可以实现随时随地进行一个学习,这样可以帮助快速走出来! 您…...
万界星空科技MES系统中的排版排产功能
在当今高度竞争的市场环境中,企业对于生产管理的效率和质量要求日益提高。作为智能制造的重要组成部分,制造执行系统(MES)以其强大的功能,在提升企业生产能力方面发挥着不可替代的作用。万界星空科技作为行业领先的智能…...
kubeadm离线部署kubernetesv1.30.0
背景:最近由于docker image获取镜像受限的问题,以及公司内部部署kubernetes受限于内部网络无法访问公网的问题,对于离线部署kubernetes成为不是十分方便。谨以此文仅供参考。 kubernetes部署节点信息 kubernetes版本 1.30.0 操作系统版本&a…...
【PYG】dataloader和densedataloader
DenseDataLoader 是专门用于处理稠密图数据的,而 DataLoader 通常用于处理稀疏图数据。两者的主要区别在于它们的输入数据格式和处理方式。DenseDataLoader 适合处理固定大小的邻接矩阵和节点特征矩阵的数据,而 DataLoader 更加灵活,可以处理…...
完美解决ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO)
已解决ERROR 1045 (28000): Access denied for user ‘root‘‘localhost‘ (using password: NO) 下滑查看解决方法 文章目录 报错问题解决思路解决方法交流 报错问题 ERROR 1045 (28000): Access denied for user ‘root‘‘localhost‘ (using password: NO) 解决思路 对…...
ForkJoinPool 简介
引言 在现代并行编程中,处理大规模任务时将任务分割成更小的子任务并行执行是一种常见的策略。Java 提供了 Fork/Join 框架来支持这一模式,其中 ForkJoinPool 是其核心组件。本文将详细介绍 ForkJoinPool 的概念、使用方法和实际应用。 1. ForkJoinPoo…...
复现YOLO_ORB_SLAM3_with_pointcloud_map项目记录
文章目录 1.环境问题2.遇到的问题2.1编译问题1 monotonic_clock2.2 associate.py2.3 associate.py问题 3.运行问题 1.环境问题 首先环境大家就按照github上的指定环境安装即可 环境怎么安装网上大把的资源,自己去找。 2.遇到的问题 2.1编译问题1 monotonic_cloc…...
Docker:Docker网络
Docker Network 是 Docker 平台中的一项功能,允许容器相互通信以及与外界通信。它提供了一种在 Docker 环境中创建和管理虚拟网络的方法。Docker 网络使容器能够连接到一个或多个网络,从而使它们能够安全地共享信息和资源。 预备知识 推荐先看视频先有…...
Ubuntu 24.04-自动安装-Nvidia驱动
教程 但在安全启动模式下可能会报错。 先在Nvidia官网找到GPU对应的驱动版, 1. 在软件与更新中选择合适的驱动 2. ubuntu自动安装驱动 sudo ubuntu-drivers autoinstall显示驱动 ubuntu-drivers devices3. 安装你想要的驱动 sudo apt install nvidia-driver-ve…...
【CSAPP】-attacklab实验
目录 实验目的与要求 实验原理与内容 实验设备与软件环境 实验过程与结果(可贴图) 实验总结 实验目的与要求 1. 强化机器级表示、汇编语言、调试器和逆向工程等方面基础知识,并结合栈帧工作原理实现简单的栈溢出攻击,掌握其基…...
docker部署onlyoffice,开启JWT权限校验Token
原来的部署方式 之前的方式是禁用了JWT: docker run -itd -p 8080:80 --name docserver --network host -e JWT_ENABLEDfalse --restartalways onlyoffice/documentserver:8 新的部署方式 参考文档:https://helpcenter.onlyoffice.com/installation/…...
Hive排序字段解析
Hive排序字段解析 在Hive中,CLUSTER BY、DISTRIBUTE BY、SORT BY和ORDER BY是用于数据分发和排序的关键子句,它们各自有不同的用途和性能特点。让我们逐一解析这些子句: 1. DISTRIBUTE BY 用途: 主要用于控制如何将数据分发到Reducer。它可…...
3101.力扣每日一题7/6 Java(接近100%解法)
博客主页:音符犹如代码系列专栏:算法练习关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ 目录 思路 解题方法 时间复杂度 空间复杂度 Code 思路 主要是基于对…...
virtualbox窗口和win10窗口的切换
1、问题: 从windows切换到虚拟机可以用快捷键 ALTTAB,但是从虚拟机到windows使用 ALTTAB 无法成功切换 2、解决方法: 按下图操作 按上面步骤设置之后,每次要从虚拟机窗口切换到windows窗口 只需要先按 CtrlAlt 跳出虚拟机窗口&…...
卫星轨道平面简单认识
目录 一、轨道平面 1.1 轨道根数 1.2 应用考虑 二、分类 2.1 根据运行高度 2.2 根据运行轨迹偏心率 2.3 根据倾角大小 三、卫星星座中的轨道平面 四、设计轨道平面的考虑因素 一、轨道平面 1.1 轨道根数 轨道平面是定义卫星或其他天体绕行另一天体运动的平面。这个平…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
