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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

LeetCode - 394. 字符串解码

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

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

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

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

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...