FDU 2021 | 二叉树关键节点的个数
文章目录
- 1. 题目描述
- 2. 我的尝试
1. 题目描述
给定一颗二叉树,树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点,那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序,并解释解题思路。

输入:3, 1, 4, 3, null, 1, 5
输出:4(图中蓝色节点是关键节点)
2. 我的尝试
这道题麻烦的地方在于输入与建树。由题意可知,输入数据是以完全二叉树形式进行输入的,因此可以考虑直接用数组来存储树,然后再遍历每一个节点并判断其是否为关键节点。
数据的输入是以空格作为分隔符的,因此不适宜直接用 cin进行读入。可以用 getline 函数读入整行,再对读入的字符串遍历进行处理。
#include <bits/stdc++.h>using namespace std;int main() {string str; // 存储输入的字符串int val = 0; // 用于计算当前输入节点的值vector<int> tree;int cnt = 0;getline(cin, str);int n = str.size();// 建树for (int i = 0; i < n; i ++) {auto c = str[i];if ('0' <= c && c <= '9') {val = val * 10 + c - '0';} else if (val) {tree.push_back(val);val = 0;} else if (c == 'n') {tree.push_back(-1);}}tree.push_back(val);n = tree.size();// 对除根节点外所有节点遍历,将其与各祖先节点比较,判断是否为关键节点for (int i = 0; i < n && tree[i] != -1; i ++) {int val = tree[i]; bool flag = true;for (int p = (i - 1) / 2; p >= 0; p = (p - 1) / 2) {if (tree[p] > val) flag = false;if (p == 0) break;}if (flag) cnt ++;}// 根节点一定为关键节点,直接加1cnt ++;cout << cnt;
}
相关文章:
FDU 2021 | 二叉树关键节点的个数
文章目录 1. 题目描述2. 我的尝试 1. 题目描述 给定一颗二叉树,树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点,那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序,并…...
精读《React Conf 2019 - Day2》
1 引言 这是继 精读《React Conf 2019 - Day1》 之后的第二篇,补充了 React Conf 2019 第二天的内容。 2 概述 & 精读 第二天的内容更为精彩,笔者会重点介绍比较干货的部分。 Fast refresh Fast refresh 是更好的 react-hot-loader 替代方案&am…...
向ChatGPT高效提问模板
PS: ChatGPT无限次数,无需魔法,登录即可使用,网页打开下面 tj4.mnsfdx.net [点击跳转链接](http://tj4.mnsfdx.net/) 我想请你XXXX,请问我应该如何向你提问才能得到最满意的答案,请提供全面、详细的建议,针对每一个建…...
android metaRTC编译
参考文章: metaRTC3.0稳定版本编译指南_metartc 编译-CSDN博客 源码下载: Releases metartc/metaRTC GitHub 版本v6.0-b4即可...
HDFS面试重点
文章目录 1. HDFS的架构2. HDFS的读写流程3.HDFS中,文件为什么以block块的方式存储? 1. HDFS的架构 HDFS的架构可以分为以下几个主要组件: NameNode(名称节点): NameNode是HDFS的关键组件之一,…...
Java中的IO流是什么?
Java中的IO流(Input/Output Stream)是Java编程语言中用于处理输入和输出操作的一种重要机制。在Java中,IO流被用来读取和写入数据,这些数据可以来自各种来源,如文件、网络连接、内存缓冲区等。Java的IO流提供了丰富的类…...
Spring boot 集成netty实现websocket通信
一、netty介绍 Netty 是一个基于NIO的客户、服务器端的编程框架,使用Netty 可以确保你快速和简单的开发出一个网络应用,例如实现了某种协议的客户、服务端应用。Netty相当于简化和流线化了网络应用的编程开发过程,例如:基于TCP和U…...
数码管的动态显示(二)
1.原理 这个十六进制是右边的dp为高位。 数码管的动态显示,在第一个计数周期显示个位,在第二个周期显示十位,在第三个周期显示百位由于人眼的视觉和数码管的特性,感觉就是显示了234,每个数码管的显示需要从输入的数据里…...
【JavaScript】数据类型转换 ① ( 隐式转换 和 显式转换 | 常用的 数据类型转换 | 转为 字符串类型 方法 )
文章目录 一、 JavaScript 数据类型转换1、数据类型转换2、隐式转换 和 显式转换3、常用的 数据类型转换4、转为 字符串类型 方法 一、 JavaScript 数据类型转换 1、数据类型转换 在 网页端 使用 HTML 表单 和 浏览器输入框 prompt 函数 , 接收的数据 是 字符串类型 变量 , 该…...
git学习(创建项目提交代码)
操作步骤如下 git init //初始化git remote add origin https://gitee.com/aydvvs.git //建立连接git remote -v //查看git add . //添加到暂存区git push 返送到暂存区git status // 查看提交代码git commit -m初次提交git push -u origin "master"//提交远程分支 …...
Day36:安全开发-JavaEE应用第三方组件Log4j日志FastJson序列化JNDI注入
目录 Java-项目管理-工具配置 Java-三方组件-Log4J&JNDI Java-三方组件-FastJson&反射 思维导图 Java知识点: 功能:数据库操作,文件操作,序列化数据,身份验证,框架开发,第三方库使用…...
HTML5+CSS3+JS小实例:全屏范围滑块
实例:全屏范围滑块 技术栈:HTML+CSS+JS 效果: 源码: 【HTML】 <!DOCTYPE html> <html lang="zh-CN"> <head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale…...
ctf杂项总结
1.文件无法打开 1.1.文件拓展名损坏/错误导致 方法: 1.使用kali当中的file命令查看,之后修改为正确的后缀即可 2.通过16进制编辑器打开查看文件头 3.文件头残缺/错误,可以先使用kail当中的file命令查看它的类型,之后再通过 16…...
openAI key 与ChatGPTPlus的关系,如何升级ChatGPTPLus
一、前言 先详细介绍一下Plus会员和Open API之间的区别: 实际上,这两者是相互独立的。举例来说,虽然您开通了Plus会员,并不意味着您就可以使用4.0版本的API。尽管这两个账户可以是同一个,但它们是完全独立的平台。 …...
KB5034441 0x80070643 reagentc.exe 无法更新引导配置数据
微软2024年1月的更新补丁正常更新会出现0x80070643错误,原因是正常安装系统默认的恢复分区留小了,通过压缩系统盘空间然后在diskgenius扩容恢复分区空间可以解决这个问题,但是笔者在进行上述操作时依旧出现了报错,按照网上的说法可…...
全网最最最详细“Jupyter command ‘jupyter-notebook‘ not found.“的解决方案
"Jupyter command jupyter-notebook not found."。这通常意味着 jupyter-notebook 命令在当前的虚拟环境中未安装或未正确安装,因此系统无法识别此命令。 原因分析 未安装 Jupyter Notebook: 可能你的虚拟环境中还没有安装 Jupyter Notebook。虽然 Jupyt…...
Java中常用的集合及方法(2)
在Java(JDK8)中,集合(Collection)是数据结构的实现,用于存储和操作对象集合。 集合(Collection)中包含的一般类或接口: 在这其中呢,我们经常使用的其实就是L…...
如何轻松打造属于自己的水印相机小程序?
水印相机小程序源码 描述:微信小程序。本文将为您详细介绍小程序水印相机源码的搭建过程,教您如何轻松打造属于自己的水印相机小程序。无论您是初学者还是有一定基础的开发者,都能轻松掌握这个教程。 一:水印相机搭建教程 1 隐…...
Qt+FFmpeg+opengl从零制作视频播放器-12.界面美化
Qt是一个跨平台的C++图形用户界面应用程序开发框架,提供了丰富的功能和工具来创建美观的界面。以下是一些方法,可以帮助美化Qt界面: 使用样式表(QSS):Qt支持通过QSS(Qt样式表)来自定义界面的外观。QSS是一种类似于CSS的语言,可以用来设置控件的颜色、字体、边框等样式…...
【测试】1. 概念 + 基础篇
概念篇 测试相较于开发岗位而言,如果同学们的编程能力稍微弱一些,可以尝试测试方向(更简单) 1. 什么是软件测试 最常见的理解是:软件测试就是找BUG,发现缺陷。 早期,人们更多的将测试看成是对…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
