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

L2-051 满树的遍历

L2-051 满树的遍历 - 团体程序设计天梯赛-练习集 (pintia.cn)

题解
  1. 数据结构选择

为了表示树的结构,我们可以使用邻接表。邻接表是一种常用的图和树的表示方法,它能够高效地存储每个节点的子节点信息。在本题中,我们可以使用一个数组 g,其中 g[i] 存储节点 i 的所有子节点。同时,使用一个数组 pre 来存储前序遍历的结果。

  1. 输入处理

  • 首先读取树中结点的个数 n

  • 接着,依次读取每个结点的父结点编号。对于每个结点 i,如果其父结点编号为 0,则说明该结点是根结点,记录其编号;否则,将结点 i 添加到其父结点的子节点列表中。

  1. 计算树的度和判断是否为 k 阶满树

  • 我们可以通过深度优先搜索(DFS)来遍历树。在遍历过程中,我们需要记录每个非叶结点的度,并找出树的最大度 k

  • 初始化 k 为根结点的度。在 DFS 过程中,如果遇到某个非叶结点的度不等于 k,则说明该树不是 k 阶满树,将标记 flag 设为 false。同时,更新 k 为所有非叶结点度的最大值。

  1. 前序遍历

  • 前序遍历的顺序是:根节点 -> 左子树 -> 右子树。在 DFS 过程中,当访问到一个节点时,将其加入到 pre 数组中,然后递归地访问其所有子节点。由于题目要求兄弟结点按编号升序访问,我们在存储子节点时会自动满足这个条件。

  1. 输出结果

  • 首先输出树的度 k

  • 根据 flag 的值,输出 yesno 表示该树是否为 k 阶满树。

  • 最后输出前序遍历序列 pre,数字间以一个空格分隔,行首尾不得有多余空格。

代码
#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;
const int N = 1e5+10;  // 定义常量 N,用于表示最大节点数
vector<int> g[N];  // 定义邻接表 g,g[i] 存储节点 i 的所有子节点
vector<int> pre;  // 定义向量 pre,用于存储前序遍历的结果
int k,root;  // 定义变量 k 表示树的度,root 表示树的根节点
bool flag=true;  // 定义布尔变量 flag,用于标记树是否为 k 阶满树
​
// 深度优先搜索函数,用于前序遍历树并判断是否为 k 阶满树
void dfs(int u){// 如果当前节点有子节点且子节点数量不等于 k,则不是 k 阶满树if(g[u].size()>0 && g[u].size()!=k){flag=false;// 更新树的度 k 为当前节点子节点数量和 k 中的较大值k=max(k,(int)g[u].size());}// 将当前节点加入前序遍历结果pre.push_back(u);// 递归遍历当前节点的所有子节点for(int i=0; i<g[u].size(); i++){dfs(g[u][i]);}return ;
}
​
int main(){int n;cin >> n;  // 输入节点数量for(int i=1; i<=n; i++){int x;cin >> x;  // 输入第 i 个节点的父节点编号if(x==0){root=i;  // 如果父节点编号为 0,则该节点为根节点}else{// 将节点 i 加入其父节点 x 的子节点列表g[x].push_back(i);}}// 初始化树的度 k 为根节点的子节点数量k=g[root].size();// 从根节点开始进行深度优先搜索dfs(root);// 输出树的度cout << k;// 根据 flag 的值输出是否为 k 阶满树if (flag)cout << " yes";else cout << " no";cout << endl;// 输出前序遍历结果for (int i = 0; i < pre.size(); i++) {if (i)cout << " ";cout << pre[i];}
}

相关文章:

L2-051 满树的遍历

L2-051 满树的遍历 - 团体程序设计天梯赛-练习集 (pintia.cn) 题解 数据结构选择 为了表示树的结构&#xff0c;我们可以使用邻接表。邻接表是一种常用的图和树的表示方法&#xff0c;它能够高效地存储每个节点的子节点信息。在本题中&#xff0c;我们可以使用一个数组 g&am…...

2025年电子电气与新材料国际学术会议

重要信息 官网&#xff1a;www.iceenm.org&#xff08;点击了解详情&#xff09; 时间&#xff1a;2025年4月25-27日 地点&#xff1a;中国-杭州 部分介绍 征稿主题 电子电气 新材料 电力电子器件和系统设计 可再生能源与电网集成技术 下一代半导体…...

数字人:打破次元壁,从娱乐舞台迈向教育新课堂(4/10)

摘要&#xff1a;数字人正从娱乐领域的璀璨明星跨界到教育领域的智慧导师&#xff0c;展现出无限潜力。从虚拟偶像、影视游戏到直播短视频&#xff0c;数字人在娱乐产业中大放异彩&#xff0c;创造巨大商业价值。在教育领域&#xff0c;数字人助力个性化学习、互动课堂和虚拟实…...

【Hyperlane 】轻松实现大文件分块上传!

【Hyperlane 】轻松实现大文件分块上传&#xff01; 痛点直击&#xff1a;大文件上传不再是难题 在云存储、音视频处理、文件协作等场景中&#xff0c;大文件上传常面临中断重试成本高、内存占用大、网络不稳定等挑战。传统方案要么复杂笨重&#xff0c;要么性能瓶颈明显。 现…...

【深入浅出 Git】:从入门到精通

这篇文章介绍下版本控制器。 【深入浅出 Git】&#xff1a;从入门到精通 Git是什么Git的安装Git的基本操作建立本地仓库配置本地仓库认识工作区、暂存区、版本库的概念添加文件添加文件到暂存区提交文件到版本库提交文件演示 理解.git目录中的文件HEAD指针与暂存区objects对象 …...

APP动态交互原型实例|墨刀变量控制+条件判断教程

引言 不同行业的产品经理在绘制原型图时&#xff0c;拥有不同的呈现方式。对于第三方软件技术服务公司的产品经理来说&#xff0c;高保真动态交互原型不仅可以在开发前验证交互逻辑&#xff0c;还能为甲方客户带来更直观、真实的体验。 本文第三部分将分享一个实战案例&#…...

第二节:React 基础篇-受控组件 vs 非受控组件

一、场景题&#xff1a;设计一个实时搜索输入框&#xff0c;说明选择依据 受控组件 vs 非受控组件 核心区别 特征受控组件非受控组件数据管理由React状态&#xff08;state&#xff09;控制通过DOM元素&#xff08;ref&#xff09;直接访问更新时机每次输入触发onChange提交…...

电脑的usb端口电压会大于开发板需要的电压吗

电脑的USB端口电压通常不会大于开发板所需的电压&#xff0c;以下是详细解释&#xff1a; 1. USB端口电压标准 根据USB规范&#xff0c;USB接口的标称输出电压为5V。实际测量时&#xff0c;USB接口的输出电压会略有偏差&#xff0c;通常在4.75V到5.25V之间。USB 2.0和USB 3.0…...

软件界面设计:打造用户喜爱的交互体验

在数字化飞速发展的当下&#xff0c;软件已渗透进生活的各个角落&#xff0c;从日常使用的社交、购物软件&#xff0c;到专业领域的办公、设计软件&#xff0c;其重要性不言而喻。而软件界面作为用户与软件交互的桥梁&#xff0c;直接决定了用户对软件的第一印象与使用体验。出…...

7、linux基础操作2

一、linux调度 1、crontab [选项] 1.1、了解 定时任务调度:指每隔指定的时间&#xff0c;执行特定的命令或程序。 基本语法&#xff1a;crontab [选项] 常用选项&#xff1a; e&#xff1a; 编辑定时任务l&#xff1a;查询定时任务r&#xff1a;删除当前用户的所有定时任务…...

大数据管理专业想求职数据分析岗,如何提升面试通过率?

从技能到策略&#xff0c;解锁高薪岗位的六大核心逻辑 在数字化浪潮席卷全球的今天&#xff0c;数据分析岗位的竞争愈发激烈。对于大数据管理专业的学生而言&#xff0c;如何从众多求职者中脱颖而出&#xff1f;本文结合行业趋势与实战经验&#xff0c;提炼出提升面试通过率的…...

移动端六大语言速记:第15部分 - 其他方面

移动端六大语言速记:第15部分 - 其他方面 本文将对比Java、Kotlin、Flutter(Dart)、Python、ArkTS和Swift这六种移动端开发语言的其他重要特性,帮助开发者全面了解各语言的独特优势和应用场景。 15.1 语言特有功能 各语言特有功能对比: 语言特有功能描述Java注解(Annotat…...

3.1.3.4 Spring Boot使用使用Listener组件

在Spring Boot中&#xff0c;使用Listener组件可以监听和响应应用中的各种事件。首先&#xff0c;创建自定义事件类CustomEvent&#xff0c;继承自ApplicationEvent。然后&#xff0c;创建事件监听器CustomEventListener&#xff0c;使用EventListener注解标记监听方法。接下来…...

基于关键字定位的自动化PDF合同拆分

需求背景&#xff1a; 问题描述&#xff1a; 我有一份包含多份合同的PDF文件&#xff0c;需要将这些合同分开并进行解析。 传统方法&#xff08;如以固定页数作为分割点&#xff09;不够灵活&#xff0c;无法满足需求。 现有方法的不足&#xff1a; 网上找到的工具大多依赖手动…...

ssh连接远程Host key verification failed.

问题描述 在对已部署的项目进行维护过程中&#xff0c;遇到的一个小问题&#xff0c;记录一下。 SSH连接云服务器ssh xxx云服务器IP地址&#xff0c;提示&#xff1a; The authenticity of host xxxxxx (xx.xxx.123.321) cant be established. ECDSA key fingerprint is SHA…...

Matlab 汽车ABS的bangbang控制和模糊PID控制

1、内容简介 Matlab 197-汽车ABS的bangbang控制和模糊PID控制 可以交流、咨询、答疑 2、内容说明 略 摘要&#xff1a;本文旨在设计一种利用模糊控制理论优化的pid控制器&#xff0c;控制abs系统&#xff0c;达到对滑移率最佳控制范围的要求 &#xff0c;所提出的方案采用级联…...

kotlin的takeIf使用

takeIf用于判断指定对象是否满足条件&#xff0c;满足就返回该对象自身&#xff0c;不满足返回null。因为可以返回对象自身&#xff0c;所以可以用作链式调用&#xff0c;以简化代码&#xff0c;又因takeIf可能返回空&#xff0c;所以常常和let结合使用&#xff0c;示例如下&am…...

MySQL 进阶 - 2 ( 9000 字详解)

一&#xff1a; SQL 优化 1.1 插入数据 1.1.1 批量插入 单条 INSERT 语句执行时&#xff0c;需经历语法解析、事务提交、磁盘 I/O 等多个步骤。批量插入将多条数据合并为一条 SQL&#xff0c;能够减少网络通信和事务开销。 -- 单条插入&#xff08;低效&#xff09; INSERT…...

Devops之GitOps:什么是Gitops,以及它有什么优势

GitOps 定义 GitOps 是一种基于版本控制系统&#xff08;如 Git&#xff09;的运维实践&#xff0c;将 Git 作为基础设施和应用程序的唯一事实来源。通过声明式配置&#xff0c;系统自动同步 Git 仓库中的期望状态到实际运行环境&#xff0c;实现持续交付和自动化运维。其核心…...

VSCode和Fitten Code

提示&#xff1a;本文为学习记录&#xff0c;若有错误&#xff0c;请联系作者。 文章目录 一、离线安装二、在线安装总结 一、离线安装 访问 Open VSX 镜像站 打开 https://open-vsx.org&#xff0c;搜索 Fitten Code 点击“从VSIX安装”&#xff0c;选择下载的VSIX即可。安装…...

在 Visual Studio Code 中安装 Python 环境

在 Visual Studio Code 中安装 Python 环境 1. 安装 Visual Studio Code 首先&#xff0c;下载并安装 Visual Studio Code&#xff08;VS Code&#xff09;&#xff1a; 下载链接&#xff1a;Visual Studio Code 官网安装步骤&#xff1a;按照下载页面的说明进行安装。 2. …...

[问题帖] vscode 重启远程终端

原理 有的时候&#xff0c;在vscode 远程ssh连接到服务器的时候&#xff0c;可能遇到需要重启终端才能生效的配置&#xff0c;比如add group的时候&#xff0c;而此时无论你是关闭vscode终端重启&#xff0c;还是reload窗口都是没用的。 因为不管你本地是否连接了远程的vscode服…...

PostgreSQL技术大讲堂 - 第86讲:数据安全之--data_checksums天使与魔鬼

PostgreSQL技术大讲堂 - 第86讲&#xff0c;主题&#xff1a;数据安全之--data_checksums天使与魔鬼 1、data_checksums特性 2、避开DML规则&#xff0c;嫁接非法数据并合法化 3、避开约束规则&#xff0c;嫁接非法数据到表中 4、避开数据检查&#xff0c;读取坏块中的数据…...

No staged files match any configured task

我在拉取一个新项目的时候&#xff0c;进行 git commit 的时候就出现了这个问题 然后我现在来说一下我出现这个问题的解决思路 我们点击 “显示命令输出” 我们把第二行的错误 subject may not be empty [subject-empty] 复制搜索一下 这是其他人写的 博客&#xff1a;subje…...

Sqlite3 查看db文件

以下是一些 SQLite3 常用命令的整理&#xff0c;涵盖数据库操作、表管理、数据查询等场景&#xff1a; 1. 数据库连接与退出 打开/创建数据库&#xff1a;sqlite3 filename.db # 打开或创建数据库文件退出 SQLite3 命令行&#xff1a;.exit # 退出 .quit …...

【leetcode hot 100 152】乘积最大子数组

错误解法&#xff1a;db[i]表示以i结尾的最大的非空连续&#xff0c;动态规划&#xff1a;dp[i] Math.max(nums[i], nums[i] * dp[i - 1]); class Solution {public int maxProduct(int[] nums) {int n nums.length;int[] dp new int[n]; // db[i]表示以i结尾的最大的非空连…...

微信小程序实时日志记录-接口监控

文章目录 微信小程序如何抓取日志&#xff0c;分析用户异常问题可查看用户具体页面行为操作web体验分析![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/dd20bb72606842128aa1eaf0881196f6.png) 腾讯小程序平台&#xff0c;提供了非常好用的&#xff0c;。 web分析工…...

【C++刷题】二叉树基础OJ题

&#x1f4dd;前言说明&#xff1a; 本专栏主要记录本人的基础算法学习以及刷题记录&#xff0c;使用语言为C。 每道题我会给出LeetCode上的题号&#xff08;如果有题号&#xff09;&#xff0c;题目&#xff0c;以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的…...

CSS高级技巧

目录 一、精灵图 二、字体图标 三、CSS制作三角形 四、CSS用户界面样式 1、鼠标样式 cursor 2、轮廓线 outline 3、防止拖拽文本域 resize 五、vertical-align 属性 六、溢出的文字省略号显示 1、单行文本溢出显示省略号 2、多行文本溢出显示省略号 七、常见布局技…...

70. 爬楼梯:动态规划

题目来源 70. 爬楼梯 - 力扣&#xff08;LeetCode&#xff09; 题目描述 思路 1.观察每个较少的台阶的方法 2.dp[0,1,2,3,5,8,13]---->dp[i]表示爬上第i阶的方法数 3.观察dp&#xff1a;dp[i]dp[i-1]dp[i-2]; 代码 public int climbStairs(int n) {int[] dp new int…...

使用治疗前MR图像预测脑膜瘤Ki-67的多模态深度学习模型

大家好&#xff0c;我是带我去滑雪&#xff01; 脑膜瘤是一种常见的脑部肿瘤&#xff0c;Ki-67作为肿瘤细胞增殖的标志物&#xff0c;对于评估肿瘤的生物学行为、预后以及治疗方案的制定具有至关重要的作用。然而&#xff0c;传统的Ki-67检测依赖于组织学切片和免疫组化染色等方…...

Skynet.socket 函数族使用详解

目录 Skynet.socket 函数族使用详解核心功能分类一、TCP 连接管理1. 监听端口2. 建立连接3. 关闭连接 二、数据读写操作1. 阻塞式读取2. 写入数据2.1 socket.write(fd, data) 的返回值2.2 示例代码2.3 关键注意事项2.4 与其他函数的区别2.5 底层原理2.6 总结 三、UDP 处理1. 创…...

Python signal 模块详解:优雅处理异步事件

诸神缄默不语-个人技术博文与视频目录 在 Linux 或类 Unix 系统中&#xff0c;信号&#xff08;Signal&#xff09;是一种用于进程间通信的机制&#xff0c;允许操作系统或其他进程向目标进程发送异步通知。 Python 的 signal 模块提供了对这些信号的访问和处理能力&#xff0…...

[LeetCode 189] 轮转数组

[LeetCode 189] 轮转数组 题目描述&#xff1a; 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 示例 2: 输入&#xff1a;nums [-1,-100,3,99], k 2 …...

【Qt】qDebug() << “中文测试“; 乱码问题

环境 Qt Creator版本&#xff1a;4.7.1 编译器&#xff1a;MSVC2015_32bit 解法一 在.pro文件中添加 msvc:QMAKE_CXXFLAGS -execution-charset:utf-8注意&#xff1a; 1、需要清理项目&#xff0c;并重新qmake&#xff0c;然后构建。 测试项目下载&#xff1a;https://do…...

解析Java根基:Object类核心方法

Object类常见方法解析 在Java编程中&#xff0c;Object类是所有类的根类&#xff0c;它包含了许多实用的方法&#xff0c;这些方法在不同的场景下发挥着重要作用。下面我们来详细了解一下Object类中的一些常见方法。 1. toString方法 toString方法是用于将对象转换为字符串表…...

最近在工作中感受到了设计模式的重要性

之前了解设计模式&#xff1a;只是应付一下面试 在之前一年多的工作中也没遇到使用场景 最近在搭建验证环境的时候&#xff0c;才发现这玩意这么重要 首先是设计模式的使用场景一定是在很复杂繁琐的场景下进行的 之所以说是复杂/繁琐的场景&#xff0c;因为一些场景也许逻辑不难…...

Docker 镜像、容器与数据卷的高效管理:最佳实践与自动化脚本20250411

Docker 镜像、容器与数据卷的高效管理&#xff1a;最佳实践与自动化脚本 引言 在现代软件开发中&#xff0c;容器化技术正变得越来越重要。Docker 作为容器化的代表工具&#xff0c;在各大企业中得到了广泛的应用。然而&#xff0c;随着容器化应用的增多&#xff0c;如何高效…...

[UEC++]UE5C++各类变量相关知识及其API(更新中)

基础变量 UE自己定义的目的&#xff1a;1.跨平台&#xff1b;2.兼容反射&#xff1b;3.方便宏替换 FString 基础赋值与初始化 遍历与内存 迭代器访问 清除系列操作 合并 插入与移除 RemoveFromStart是从开头看&#xff0c;没有则移除失败返回false&#xff1b; RemoveFromEnd是…...

C++中的设计模式

设计模式是软件工程中用于解决常见问题的可复用解决方案。它们提供了一种标准化的方法来设计和实现软件系统&#xff0c;从而提高代码的可维护性、可扩展性和可重用性。C 是一种支持多种编程范式&#xff08;如面向对象、泛型编程等&#xff09;的语言&#xff0c;因此可以方便…...

Java 设计模式:装饰者模式详解

Java 设计模式&#xff1a;装饰者模式详解 装饰者模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;它通过动态地为对象添加新功能&#xff0c;扩展其行为&#xff0c;而无需修改原有类的代码。装饰者模式遵循“开闭原则”&#xff0c;提供了比…...

C++ 大数相加(简要版)

#include <algorithm> #include <iterator> class Solution { public:/*** 计算两个数之和* param s string字符串 表示第一个整数* param t string字符串 表示第二个整数* return string字符串*/string solve(string s, string t) {// 处理空字符串的情况&#xf…...

Spring IoC深度解析:掌控Bean存储艺术与分层架构的智慧​​

一、IoC的本质&#xff1a;从"造物主"到"使用者"的思维跃迁 在传统编程中&#xff0c;开发者像"造物主"一样亲手创建每个对象&#xff08;new UserController()&#xff09;&#xff0c;并管理它们的依赖关系。这种方式导致代码高度耦合&#xf…...

8.4 容器2

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的 8.4.3 TabControl&#xff08;选项卡&#xff09;控件 TabControl控件可以通过设置多个选项卡页&#xff08;TabPage控件&#xff09…...

一组可能的机器学习问题列表

线性回归与多项式拟合的关系最小二乘法在机器学习中的应用梯度下降是如何实现的贝叶斯分类器的应用场景高斯分布与判定在哪里用到模型的评估有哪些参数误差中的偏差和方差定义训练集分组的快捷方式如何度量模型性能查准率查全率的定义roc,aux的含义正则化是什么意思k均值用来解…...

Android 权限列表

权限名称描述android.permission.ACCESS_CHECKIN_PROPERTIES访问登记属性读取或写入登记 check-in 数据库属性表的权限android.permission.ACCESS_COARSE_LOCATION获取粗略位置通过 WiFi 或移动基站的方式获取用户粗略的经纬度信息&#xff0c;定位精度大概误差在 30~1500 米an…...

探索在视频深度伪造中的细微的表情变化或对特定面部特征的小改动检测方法

概述 2019 年&#xff0c;美国众议院议长南希佩洛西成为了一次针对性的、技术含量相对较低的“深度伪造”式攻击的目标。真实的佩洛西视频被编辑&#xff0c;让她看起来像是喝醉了酒。这一不真实的事件在真相大白之前被分享了数百万次&#xff0c;而且在一些人没有关注后续报道…...

调用阿里云API实现身份证文字识别

TOC# 1.作者介绍 姚元帅&#xff0c;男&#xff0c;西安工程大学电子信息学院&#xff0c;2024级研究生 研究方向&#xff1a;机器视觉与人工智能 电子邮件&#xff1a;3183969029qq.com 乔幸荣&#xff0c;女&#xff0c;西安工程大学电子信息学院&#xff0c;2024级研究生&a…...

使用UFW+IPSET禁用海外IP配置持久化操作

上一章我们介绍了如何使用ufwipset禁用海外IP&#xff0c;但是如果服务器重启动&#xff0c;之前的配置就无效了&#xff0c;所以让配置持久化可以避免我们反复设置的麻烦。 IPSET配置持久化的方法有很多种&#xff0c;目前我配置成的是设置ipset后台服务&#xff0c;具体方法…...

深入Linux内核理解socket的本质

本文将从一个初学者的角度开始聊起&#xff0c;让大家了解 Socket 是什么以及它的原理和内核实现。 一、Socket 的概念 Socket 就如同我们日常生活中的插头与插座的连接关系。在网络编程中&#xff0c;Socket 是一种实现网络通信的接口或机制。 想象一下&#xff0c;插头插入…...