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

PAT甲级 1110 Complete Binary Tree

题目链接

PAT甲级 1110 Complete Binary Tree

思路

第一次的写法不是很好。
对于这种完全二叉树的层序遍历,比较烦人的就是空孩子使得处理很麻烦。
思来想去还是把空位置也入队比较好。

这样的话,访问到空指针的时机被推迟了一个level
而完全二叉树的叶子之间的层间距不会超过1
所以对于合法的完全二叉树,我们访问到空孩子的时机不会早于访问树中的任何叶节点

这样的话,当访问到空指针的时候:

  1. 对于合法的完全二叉树,一定树中所有元素都遍历完了,故有n == 0
  2. 若此时仍有n > 0,否则就说明层间有空隙,故不合法。

所以只要在访问到空指针的时候加入我们的判断即可,并记录还未访问的树节点个数。

代码

#include<bits/stdc++.h>using namespace std;vector<int> parent;
vector<pair<int, int>> children;int last = -1;int main() {int n;cin >> n;children.resize(n + 1, {-1, -1});parent.resize(n + 1, -1);for(int i = 0; i < n; ++i) {string left, right;cin >> left >> right;if(left != "-") {children[i].first = stoi(left);parent[stoi(left)] = i;}if(right != "-") {children[i].second = stoi(right);parent[stoi(right)] = i;}}int root = -1;for(int i = 0; i < n; ++i) {if(parent[i] == -1) {root = i;break;}}assert(root != -1);queue<int> q;q.push(root);bool flag = true;while(! q.empty() && flag) {int size = q.size();int pre_is_null = 0;while(size--) {auto node = q.front();q.pop();if(node == -1) {if(n > 0) {flag = false;}break;}last = node;--n;auto left = children[node].first;auto right = children[node].second;q.push(left);q.push(right);}}if(! flag) {cout << "NO " << root;} elsecout << "YES " << last;cout << endl;
}

相关文章:

PAT甲级 1110 Complete Binary Tree

题目链接 PAT甲级 1110 Complete Binary Tree 思路 第一次的写法不是很好。 对于这种完全二叉树的层序遍历&#xff0c;比较烦人的就是空孩子使得处理很麻烦。 思来想去还是把空位置也入队比较好。 这样的话&#xff0c;访问到空指针的时机被推迟了一个level 而完全二叉树的…...

【JavaSE】逻辑控制语句

文章目录一. 顺序结构二. 分支结构1. if 语句2. switch 语句3、循环结构3.1 while 循环3.2 do while 循环3.3 for 循环3.4 break 和 continue三. 输入输出1. 输出到控制台2. 从键盘输入一. 顺序结构 顺序结构比较简单&#xff0c;即程序按照代码书写的顺序一行一行执行下去。 …...

Motionbuilder系统文件说明

安装路径 Motionbuilder 默认的安装路径在 C:\Program Files\Autodesk\MotionBuilder\ 用户数据(user data) 位于安装路径下的 bin\config 非管理员用户的配置文件路径 Motionbuilder会将配置文件备份到 \Users[user]\AppData\Local\Autodesk[MotionBuilder] 当用户第一次打开…...

【我的Android开发】AMS中Activity栈管理

概述 Activity栈管理是AMS的另一个重要功能&#xff0c;栈管理又和Activity的启动模式和startActivity时所设置的Flag息息相关&#xff0c;Activity栈管理的主要处理逻辑是在ActivityStarter#startActivityUnchecked方法中&#xff0c;本文也会围绕着这个方法进进出出&#xf…...

C++源程序的构成————学习笔记

以下内容为&#xff0c;在学校上课时的课堂总结&#xff0c;偶尔我也会扩展一些内容内容仅供参考&#xff0c;欢迎大佬的指正简单的C程序#include <iostream> using namespace std;int main() {int x0;int y 0;cout << "请输入x,y的值"<<endl;cin…...

Spark Catalyst

Spark Catalyst逻辑计划逻辑计划解析逻辑计划优化Catalyst 规则优化过程物理计划Spark PlanJoinSelection生成 Physical PlanEnsureRequirementsSpark SQL 端到端的优化流程&#xff1a; Catalyst 优化器 : 包含逻辑优化/物理优化Tungsten : Spark SQL的优化过程 : 逻辑计划 …...

element 远程搜索下拉加载

created() { this.getList(); this.getGroupList(); }, directives: { /** 下拉框懒加载 */ “el-select-loadmore”: { bind(el, binding) { const SELECTWRAP_DOM el.querySelector( “.el-select-dropdown .el-select-dropdown__wrap” ); SELECTWRAP_DOM.addEventListener…...

空间复杂度与顺序表的具体实现操作(1)

最近更新的少&#xff0c;主要是因为参加了ACM竞赛空间复杂度空间复杂度也是一个数学表达式&#xff0c;是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间&#xff0c;因为这个也没太大意义&#xff0c;所以空间复杂度算的是变量…...

【springmvc】Rest ful风格

RESTful 1、RESTful简介 REST&#xff1a;Representational State Transfer&#xff0c;表现层资源状态转移。 a>资源 资源是一种看待服务器的方式&#xff0c;即&#xff0c;将服务器看作是由很多离散的资源组成。每个资源是服务器上一个可命名的抽象概念。因为资源是一…...

华为OD机试真题Python实现【用户调度】真题+解题思路+代码(20222023)

用户调度 题目 在通信系统中有一个常见的问题是对用户进行不同策略的调度,会得到不同系统消耗的性能。 假设由N个待串行用户,每个用户可以使用A/B/C三种不同的调度策略。 不同的策略会消耗不同的系统资源,请你根据如下规则进行用户调度,并返回总的消耗资源数。 规则是: …...

JavaSE学习笔记总结day19

今日内容 二、线程安全的集合 三、死锁 四、线程通信 五、生产者消费者 六、线程池 零、 复习昨日 创建线程的几种方式 1) 继承 2) 实现Runnable 3) callable接口 Future接口 4) 线程池 启动线程的方法 start() 线程的几种状态 什么是线程不安全 setName getName Thread.curr…...

FreeSql使用

目的: 1.方库分表 2.主从分离 3.分布式事务 过程&#xff1a; 官网&#xff1a;指南 | FreeSql 官方文档 1.Startup.cs 添加配置&#xff08;本地数据库MySql&#xff09; ConfigureServices&#xff1a; Func<IServiceProvider, IFreeSql> fsql r >{IFreeSql …...

Hadoop集群搭建,基于3.3.4hadoop和centos8【图文教程-从零开始搭建Hadoop集群】,常见问题解决

Hadoop集群搭建&#xff0c;基于3.3.4hadoop和centos8【小白图文教程-从零开始搭建Hadoop集群】&#xff0c;常见问题解决Hadoop集群搭建&#xff0c;基于3.3.4hadoop1.虚拟机的创建1.1 第一台虚拟机的创建1.2 第一台虚拟机的安装1.3 第一台虚拟机的网络配置1.3.1 主机名和IP映…...

UE4 材质学习 (焚烧材质)

效果步骤随便从网上下载一张图片&#xff08;地址&#xff1a;链接/链接&#xff09;&#xff0c;导入UE中新建一个材质函数这里命名为“E_Function”双击打开该材质函数&#xff0c;由于需要输出变发光和变透明两种效果&#xff0c;因此这里需要两个输出节点&#xff1a;分别命…...

【c++】STL常用算法2—常用查找算法

文章目录常用查找算法findfind_ifadjacent_findbinary_searchcountcount_if常用查找算法 算法简介&#xff1a; find//查找元素 find_if//按条件查找元素 adjacent_find//查找相邻重复元素 binary_search//二分查找法 count//统计元素个数 count_if//按条件统计元素个数find …...

史上最全最详细的Java架构师成长路径图,程序员必备

从新手码农到高级架构师&#xff0c;要经过几步&#xff1f;要多努力&#xff0c;才能成为为人倚重的技术专家&#xff1f;本文将为你带来一张程序员发展路径图&#xff0c;但你需要知道的是&#xff0c;天下没有普适的道理&#xff0c;具体问题还需具体分析&#xff0c;实践才…...

第五章 事务管理

1.事务概念 *什么是事务&#xff1a;事务是数据库操作最基本单元&#xff0c;逻辑上是一组操作&#xff0c;要么都成功&#xff0c;要么都失败 *事务的特性&#xff08;ACID&#xff09;&#xff1a;原子性、隔离性、一致性、持久性 2.搭建事务操作环境 *模拟场景&#xff…...

Redis:主从同步

Redis&#xff1a;主从同步一. 概述二. 原理(1) 全量同步(2) 增量同步(3) 优化Redis主从集群三. 总结一. 概述 引入&#xff1a; Redis主从集群采用一个Master负责写&#xff0c;多个Slave负责读的方式&#xff08;读多写少&#xff09;&#xff0c;那么如何让读取数据时多个从…...

Unity Animator.Play(stateName, layer, normalizedTime) 播放动画函数用法

原理 接口&#xff1a; public void Play(string stateName, int layer -1, float normalizedTime float.NegativeInfinity);参数含义stateName动画状态机的某个状态名字layer第几层的动画状态机&#xff0c;-1 表示播放第一个状态或者第一个哈希到的状态normalizedTime从s…...

python学习——【第三弹】

前言 上一篇文章 python学习——【第二弹】中学习了python中的运算符内容&#xff0c;这篇文章接着学习python中的流程控制语句。 流程控制指的是代码运行逻辑、分支走向、循环控制&#xff0c;是真正体现我们程序执行顺序的操作。流程控制一般分为顺序执行、条件判断和循环控…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...