当前位置: 首页 > 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;是真正体现我们程序执行顺序的操作。流程控制一般分为顺序执行、条件判断和循环控…...

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

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

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...