二叉树之层序遍历（牛客round92—

链接E-小红的ds题_牛客周赛 Round 92来源牛客网题目描述\hspace{15pt}小红希望你构造一棵层数为 nnn 的二叉树其第 iii 层恰好有 aia_iai 个节点。你能帮帮她吗\hspace{15pt}一棵树被称为二叉树当且仅当其满足∙ \hspace{23pt}\bullet\,∙每个节点要么没有父节点连接此时该节点被称为根节点、要么被 111 个父节点连接此时该节点被称为父节点的子节点∙ \hspace{23pt}\bullet\,∙每个节点连接的子节点数量要么为 000此时该节点被称为叶子节点、要么小于等于 222此时该节点被称为分支节点。输入描述:\hspace{15pt}第一行输入一个正整数 n(1≦n≦104)n \left(1 \leqq n \leqq 10^4\right)n(1≦n≦104)代表二叉树的层数。 \hspace{15pt}第二行输入 nnn 个正整数 a1,a2,…,an(1≦ai≦105)a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^5\right)a1,a2,…,an(1≦ai≦105)代表二叉树的第 iii 层的节点数量限制。保证 a11a_1 1a11且对于 2≦i≦n2 \leqq i \leqq n2≦i≦n均有 ai≦ai−1×2a_i \leqq a_{i-1} \times 2ai≦ai−1×2。 \hspace{15pt}除此之外保证单个测试文件的 aia_iai 之和不超过 10510^5105。输出描述:\hspace{15pt}第一行输出一个正整数 p(1≦p≦n)p \left(1 \leqq p \leqq n\right)p(1≦p≦n)代表根结点的编号。编号从 111 开始。 \hspace{15pt}此后输出 ∑i1nai\sum\limits_{i1}^n a_ii1∑nai 行第 iii 行输出两个元素 li,ril_i,r_ili,ri分别代表 iii 号节点的左儿子和右儿子的编号。特别的如果不存在左儿子/右儿子则输出 −1-1−1 替代这个编号。 \hspace{15pt}如果存在多个解决方案您可以输出任意一个系统会自动判定是否正确。注意自测运行功能可能因此返回错误结果请自行检查答案正确性。示例1输入复制3 1 2 33 1 2 3输出复制4 -1 -1 1 -1 6 5 2 3 -1 -1 -1 -14 -1 -1 1 -1 6 5 2 3 -1 -1 -1 -1说明完整题目可以跳转一下官方题解给的很清晰了题目也清晰。不过确实喜欢这道题姑且讲讲也提高自己。阅读题意每一层有限定的节点那么我们需要先安排那些节点编号在哪一层我们直接顺序遍历从上到下从左到又从123.......int cnt0; vectorvectorintf(n5); for(int i1;in;i){ cina[i]; ka[i]; for(int j0;ja[i];j)f[i].push_back(cnt); }f[i]的意思是第几层里面装的每一层所有节点的编号。那么第二步就是分配咯。二叉树每一个节点只能最多有叶子节点2个怎么分配上下两层都从左到右咯。那么我们用mx来记录下一层的节点数量也就是这一层需要对接的节点数量同时我们需要保证这个节点的儿子不超过两个。vectorvectorintg(n5); for(int i1;in-1;i){ int mxa[i1],now0;//这一层节点需要对接的叶子节点 for(int j0;jf[i].size();j){ if(nowmxg[f[i][j]].size()2)g[f[i][j]].push_back(f[i1][now]),now;//加入下一层的节点now来记录加到第几个 if(nowmxg[f[i][j]].size()2)g[f[i][j]].push_back(f[i1][now]),now;//加入下一层的节点now来记录加到第几个 //写两个是因为一个节点最多进入两个if我们刚好让他一次走完 } }用now来记录这一层对接下一层到了那个位置到了mx-1可以停止因为nowmx-1时候就是加入了mx个节点。同时g[i][j]的表达第i层第j个节点的儿子节点我们将儿子节点存入后续答案从这里输出这个节点的儿子节点数量也从这里判断。cout 1 endl; //定1是根 for(int i 1; i k; i){ if(g[i].size() 2) cout g[i][0] g[i][1] endl; else if(g[i].size() 1) cout g[i][0] -1 endl; else cout -1 -1 endl; }本题得解很基础的层序二叉树遍历记得开两个二维是真的数据变量多。附上完整代码

企业数字化 ERP 产品动态

相关推荐

Trae Agent 离线模式：不联网也能跑通 Agent 的三步教程

Trae Agent 离线模式：不联网也能跑通 Agent 的三步教程【免费下载链接】trae-agent Trae Agent is an LLM-based agent for general purpose software engineering tasks. 项目地址: https://gitcode.com/gh_mirrors/tr/trae-agent 公司内网与外网完全隔离&… · 2026/11/4 15:39:43

NapCatQQ 上手指南：基于 NTQQ 的 OneBot 11 机器人框架，从启动到接群管 Bot

NapCatQQ 上手指南：基于 NTQQ 的 OneBot 11 机器人框架，从启动到接群管 Bot 【免费下载链接】NapCatQQ Modern protocol-side framework based on NTQQ 项目地址: https://gitcode.com/gh_mirrors/na/NapCatQQ NapCatQQ 是一个跑在 Windows 上的 … · 2026/11/4 15:39:43

【IDEA】插件篇

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 15:39:43

MTP 推测解码 vs Mobius 知识-推理解耦：书生 S2 家族的两条提速路线，哪条更香

MTP 推测解码 vs Mobius 知识-推理解耦：书生 S2 家族的两条提速路线，哪条更香【免费下载链接】Intern-S2-397B 项目地址: https://ai.gitcode.com/InternLM/Intern-S2-397B 自研模型的军备竞赛走到今天，单纯堆参数已经不再是最性感的… · 2026/11/4 16:13:00

class-validator 验证的5个开关：如何让错误只出现在该出现的地方

class-validator 验证的5个开关：如何让错误只出现在该出现的地方【免费下载链接】class-validator Decorator-based property validation for classes. 项目地址: https://gitcode.com/gh_mirrors/cl/class-validator 更新用户资料的接口，有时 a… · 2026/11/4 16:11:59

March7thAssistant 上手指南：3 步跑通星穹铁道日常自动化

March7thAssistant 上手指南：3 步跑通星穹铁道日常自动化【免费下载链接】March7thAssistant 日常交给三月七，开拓留给你。《崩坏：星穹铁道》开源自动化助手。项目地址: https://gitcode.com/gh_mirrors/ma/March7thAssistant March… · 2026/11/4 16:11:59

Boxer CLI参数速查表：从阈值到精度，所有命令行选项一次讲透

【免费下载链接】boxer Code for the Boxer research paper 项目地址： https://gitcode.com/gh_mirrors/boxer13/boxer 点击查看免费下载 Boxer 是一个将开放世界 2D 检测框"抬升"（lifting）为 3D 方向包围盒（OBB&… · 2026/11/4 16:11:59

REA：本地 AI 逆向工程指南，用 1 条命令看清竞品应用的内部实现

REA：本地 AI 逆向工程指南，用 1 条命令看清竞品应用的内部实现【免费下载链接】rea Reverse engineer anything with agents, from app behavior down to native binaries. 项目地址: https://gitcode.com/GitHub_Trending/rea2/rea 你在别人的 … · 2026/11/4 16:11:59

chinese-xinhua 完整指南：免费构建中文语言知识库的终极方案

chinese-xinhua 完整指南：免费构建中文语言知识库的终极方案【免费下载链接】chinese-xinhua :orange_book: 中华新华字典数据库。包括歇后语，成语，词语，汉字。项目地址: https://gitcode.com/gh_mirrors/ch/chinese-xinhua … · 2026/11/4 16:10:58