聊起天梯赛L2级别的题目很多刷过PTA的同学都有一肚子话要说。L2不像L1那样基本靠模板和细心就能拿分也不像L3那样需要硬啃高级算法它卡在中间位置考得最多的反而是“基础数据结构你究竟熟不熟练”。L2—051“满树的遍历”就是特别典型的一道题。我第一次见它是在天梯赛模拟训练里看完题第一反应是“这不就是层序遍历加判断满二叉树嘛”结果真上手写建树时脑袋里没理清存储结构找根节点又踩了一脚坑白白折腾了小半个钟头。这篇题解就把我完整的解题思路、核心代码、边界条件处理和踩坑记录都整理出来给正在准备天梯赛、或者复习树的遍历这类经典题型的同学做个参考。这类题值不值得专门写一篇我的看法是非常值得。它表面考的是“满树”和“遍历”两个词实际上把树的存储、根节点确定、递归/非递归遍历、全局状态判断、输出格式控制这些点全串起来了。任何一环没想清楚代码写起来都会别扭。而且这种题在L2里具有很强的代表性把这道题吃透同一批“给树结构、判断性质、按序输出”的题目基本都能顺手拿下。1. 这道题到底在问什么1.1 拆开“满树”两个字来理解先说“满树”这个概念。竞赛里最常见的定义是满二叉树一棵二叉树中所有非叶子节点都恰好有两个孩子所有叶子节点在同一层这棵树就是满二叉树。但注意题目名字写的是“满树”有些语境下也会把它扩展到m叉满树也就是每个非叶子节点都有同样数量的孩子。不管哪种定义核心判断点都是同一个只要一个节点不是叶子那么它的孩子数量必须等于题目要求的那个固定值。对二叉树来说这个值就是2对三叉树就是3。我习惯先把判定条件写成伪代码遍历每个节点如果它的孩子数量大于0但又不等于允许的那个k值那么整棵树就不可能是满树。这个条件看起来简单但它要求你在遍历过程中不能提前退出遍历流程因为就算已经判断出不是满树了题目如果要求输出遍历序列你仍然得把整棵树完整走一遍。这个问题在考场上很容易被忽略很多人一发现“不满足满树条件”就直接return结果遍历序列输出不全送掉一大半分数。还有一个细节是单节点树算不算满树。按照常见的满二叉树定义只有一个根节点且没有孩子的树是满树因为它没有非叶子节点条件天然成立。我在多个OJ上测过类似题目绝大多数判题数据都认这个结论。不过保险起见你可以在代码里单独处理一下N1的情况至少不要让空树或者单节点这种边界数据把你卡住。1.2 输入输出结构的通用套路虽然每次天梯赛题面在排版上会有细节差异但L2的树类题目输入格式高度相似最常见的是两种。第一种第一行给一个正整数N表示节点总数接下来N行里第i行的第一个数字k表示节点i有几个孩子后面跟着k个整数表示它所有孩子的编号。第二种直接给每个节点的左右孩子编号没有孩子的节点用0或-1占位。“满树的遍历”这道题多数题解和训练版本的输入都采用了第一种孩子列表形式。这种格式的好处是建树非常直观数组下标就是节点编号vector里存孩子编号不需要额外写结构体。坏处是它不会直接告诉你根节点是谁你必须自己从输入里推断这个点我在后面专门展开。输出部分常见的题型要求有两种可能一种只输出判断结果满树输出YES否则输出NO另一种要求输出某种遍历序列比如先序遍历、层序遍历。最稳妥的做法是把判断题和遍历题合并处理遍历整棵树的同时设置一个全局标记最后根据标记决定输出内容。这样就无论题目要求输出哪种格式你的代码骨架都不用大改。1.3 考场上怎么读题最快我见过不少同学一拿到题就开始敲读写代码框架结果搞了半天才发现题意理解偏了。这里分享一个我自己的习惯拿到L2树题先花三分钟在草稿纸上回答三个问题。第一输入里有没有直接给根节点如果没有我该用什么方法找根。第二题目要求输出的遍历序列是哪一种先序、后序还是层序这决定了我选BFS还是DFS。第三满树的判定条件里非叶子节点允许的孩子数量是“恰好2”还是“每层节点数等于2的层数次方”这两种判定方式用代码实现时差别很大。把这三个问题写在纸上再动笔写代码效率会高很多。尤其第三个问题很多人知道满二叉树可以“用层序节点数量判断”但实际写起来每层节点计数需要额外维护层号比直接检查孩子数量麻烦得多。除非题目明确告诉你这是一棵二叉树且只需要判断二叉树满不满足性质否则我更推荐用“检查每个非叶子节点孩子数”这种方式通用性更强代码也更短。2. 建树之前先想明白的几件事2.1 为什么我推荐用vector数组而不是链式结构很多人在学校数据结构课上学树的时候习惯用结构体加指针的方式建二叉树比如struct Node { int val; Node *left, *right; }。这种写法在考试里不能说错但在PTA这种限时场景下它并不是最优选择。主要原因有三个一是链表方式需要频繁new节点内存分配耗时且容易出现野指针问题二是题目输入给的是节点编号不是节点对象你还要维护一个指针数组来索引三是后续遍历、找父亲、统计孩子数都要通过指针跳转代码量明显变长。我建议直接用vectorint children[MAXN]这样的数组存储MAXN根据题目N的范围开比如100005。每个节点的孩子编号直接push到这个vector里访问孩子只要遍历这个vector就行。这样做查询孩子的时间复杂度和链表方式一样是O(总孩子数)但代码简洁程度高一个档次而且在找根节点的时候只需要额外开一个bool hasFather[MAXN]数组标记每个节点是否有父亲不用遍历整棵树找parent指针。2.2 找根节点谁没有爸爸谁就是根前面提到孩子列表输入方式不会直接告诉你根节点需要自己找。找法其实非常简单读入每一行时把孩子编号对应的hasFather标记置为true。所有输入读完之后从1到N扫一遍找到唯一一个hasFather为false的节点它就是根。这个办法也能顺带检查数据合法性如果扫完发现有两个节点都没有父亲说明输入数据有问题或者题目给的是一棵森林而不是一棵树。这里有一个容易踩的坑有些题目的节点编号是0到N-1有些是1到N。如果你习惯了1到N碰到从0开始的题就很容易数组越界或者漏扫。我自己的习惯是先把样例数据手动模拟一遍确认起始编号再定循环边界。还有根节点的位置不一定在输入的第一行不要预设第1个节点是根否则遇到根编号靠后的数据就挂了。2.3 满树判断的两种等价写法判断满树理论上可以走两条路。第一条是我前面说的遍历每个节点检查它是否满足“没有孩子或者孩子数量等于固定值k”。这条路写起来直接一个if就能搞定。第二条是从定义出发用层序遍历记录每一层的节点数检查每一层节点数是否都等于2的层数次方。这条路虽然也正确但实现起来要额外维护深度信息代码量增加不少而且只对二叉树有效换成“每个非叶子节点有三个孩子”的满三叉树就得重新推导节点数量公式。我强烈建议用第一种写法因为它体现了“满树”最本质的定义节点自由度的一致性。判断时只需要注意一点就是当你发现某个节点不满足条件时不能直接return退出遍历因为后续还要输出遍历序列。正确做法是设置一个全局布尔变量比如bool isFull true发现不满足就把它置为false然后继续遍历完所有节点。3. 遍历与判断的完整代码拆解3.1 核心代码模板下面这份代码是我在现场做题时整理出来的模板输入格式按前面说的“第一行N接下来N行每行先给孩子数k再给k个孩子编号”来处理。代码同时做了两件事DFS先序遍历整棵树并且在遍历过程中判断满树条件。如果读题之后确定只需要层序输出把DFS改成BFS队列就行满树判断逻辑完全不用变。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint children[MAXN]; bool hasFather[MAXN]; bool isFull true; // 先序遍历同时检查满树条件 // 这里k是要求的非叶子节点孩子数二叉树为2 void dfs(int u, int k) { // 当前节点不是叶子但孩子数量不等于k说明不是满树 if (!children[u].empty() (int)children[u].size() ! k) { isFull false; } // 递归遍历所有孩子 for (int v : children[u]) { dfs(v, k); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, k; // 有些题面会直接给k如果没有就给2 cin N k; for (int i 1; i N; i) { int cnt; cin cnt; children[i].resize(cnt); for (int j 0; j cnt; j) { cin children[i][j]; hasFather[children[i][j]] true; } } // 找根节点 int root -1; for (int i 1; i N; i) { if (!hasFather[i]) { root i; break; } } if (root -1) { cout NO endl; return 0; } dfs(root, k); cout (isFull ? YES : NO) endl; return 0; }这段模板最核心的地方就是dfs函数里那个判断它把“遍历输出”和“满树标记”耦合在同一个递归过程中既保证了即使发现不是满树也会继续走完所有节点又避免了额外写一遍遍历代码。3.2 逐段解释关键逻辑先看children[i].resize(cnt)这行。为什么要先resize再逐个读入因为后面的范围for循环for (int v : children[u])依赖vector的长度你先分配好空间读入数据时就不用push_back而直接用下标赋值能在数据量大的时候省一点vector扩容开销。坦白说这个优化在天梯赛的数据量下影响不大但是能养成好习惯到L3某些卡常数的题时会受益。再看找根节点的部分。我初始化root -1扫描过程中一旦遇到hasFather[i] false就赋值并break。如果最后root仍然是-1说明所有节点都有父亲输入肯定有环直接判NO退出。这里其实暗含了一个假设输入数据的节点编号是连续的1到N并且构成单棵树。万一题目给的是森林这个findRoot会扫描到第一个无父亲节点后面的节点不会管这时如果直接按根去DFS会漏掉另一棵树。不过天梯赛L2的树题基本默认是单棵树真遇到森林题目一般会说清楚。isFull变量我放在全局避免在递归函数里传引用或者返回值。这样写有一个好处递归函数签名保持简单不容易出错。坏处是如果代码需要并行处理多棵树全局变量的方式就不合适了。竞赛场景下并行是不存在的所以全局变量反而是最省事的选择。最后看cout (isFull ? YES : NO)。有些同学喜欢在dfs内部直接判断并输出比如发现不是满树立马printf。这种做法一旦题目要求“不管满不满都要先输出遍历序列”输出顺序就会被打乱。把判断结果延迟到最终输出逻辑上更安全。4. 层序遍历输出时的细节处理4.1 队列的选型和BFS模板如果题目需要输出层序遍历序列代码主体需要从DFS换成BFS。BFS实现树遍历比图遍历简单因为不需要判重每个节点只会被入队一次。我习惯直接用标准库队列queueint没有必要自己手写循环队列天梯赛的数据量用STL完全不会超时。下面是一个通用的BFS层序收集模板vectorint levelOrder; queueint q; q.push(root); while (!q.empty()) { int u q.front(); q.pop(); levelOrder.push_back(u); for (int v : children[u]) { q.push(v); } }注意这个BFS只要求“按层输出”并不关心每一层从哪里断开。如果题目要求把每一层单独一行输出就需要在while循环内部加一层“当前队列长度”控制while (!q.empty()) { int sz (int)q.size(); for (int i 0; i sz; i) { int u q.front(); q.pop(); cout u ; for (int v : children[u]) q.push(v); } cout endl; }这个“队列快照长度”的技巧在处理“按层输出二叉树”“打印树的每层节点”这类改编题时几乎是万能解法。它的原理是进入for循环前队列里恰好存放着当前层的全部节点此时记录szfor循环内部只弹sz次那么新入队的节点不会被当前层消费留到下一轮while循环再处理。4.2 输出格式控制不仔细会白丢分天梯赛对输出格式的检查非常严格多一个空格、少一个换行都可能被判Presentation Error甚至Wrong Answer。我见过太多同学算法写对了结果因为输出格式错误反复WA。这里有几个通用经验如果题目要求“同一行节点之间用空格隔开”我通常采用“先输出第一个节点后面的节点前面加空格”的方式或者把节点暂存在vector里最后统一输出。第二种方式最稳遍历结果全存进一个vector然后单独写一段输出代码for (int i 0; i (int)levelOrder.size(); i) { if (i 0) cout ; cout levelOrder[i]; } cout endl;这个写法比在每个节点输出后加空格要安全因为它天然规避了行尾多余空格的问题。很多人在树上栽跟头不是算法问题而是这种“肉眼看不出来”的格式细节。竞赛判题不会给你任何提示所以最好的策略就是从模板层面消灭犯错的可能。5. 现场踩过的坑和排查记录5.1 常见问题速查表我把程设竞赛里树遍历相关题目最容易出问题的点整理成一个速查表这些都是真实会遇到的不是理论上的风险。现象原因解决办法遍历序列少了一部分节点发现不是满树后提前return用全局变量标记遍历必须全量完成根节点找错默认第一个节点就是根用hasFather数组扫描数组越界节点编号从0开始但循环从1开始先看样例输入确认编号起始值递归栈溢出树深度过大递归层数太多改成迭代DFS或BFS输出格式错误行尾多空格用vector暂存序列再统一输出满树判断错误用“每层节点数”判断时边界写错改用“非叶子节点孩子数等于k”判断STL超时没用快读且大量使用endl加ios::sync_with_stdio(false)用\n替代endl5.2 递归栈溢出和CLOSE_WAIT一样烦很多人以为树递归不会爆栈因为二叉树深度平均是logN量级。但注意天梯赛里的“树”不一定是平衡的如果输入给的是一条链状结构比如每个节点只有一个孩子那么递归深度会达到N的级别。N如果到10^5甚至10^6递归层数超过系统默认栈空间程序就会直接RE。解决方法是把DFS改成显式栈的迭代写法。树遍历迭代写法和图的DFS迭代非常像区别只是不需要visited数组因为树结构天然没有环。用栈模拟先序遍历可以这样写vectorint preOrder; stackint st; st.push(root); while (!st.empty()) { int u st.top(); st.pop(); preOrder.push_back(u); // 注意为了让孩子按照输入顺序输出需要逆序入栈 for (int i (int)children[u].size() - 1; i 0; i--) { st.push(children[u][i]); } }这段代码有个小细节先序遍历要求“根、左、右”的顺序如果用栈模拟为了先遍历第一个孩子就得把后面的孩子先压栈、第一个孩子最后压栈这样弹栈时才能先访问第一个孩子。如果孩子顺序对最终输出没有要求逆序入栈可以省略但既然做题输出顺序还是尽量和递归版本保持一致比较好。5.3 一个容易忽略的全局变量陷阱isFull这种全局变量在一次运行里只会用一次但如果你的代码里有多组测试数据比如题目用while (cin N)循环读入那么每组数据处理完之后必须重置isFull为true同时清空children数组和hasFather数组。很多选手在单组测试的题目上顺利通过一到多组测试就翻车问题基本都出在这个重置环节。我处理多组数据的习惯是每组数据开头把用到的全局数组遍历一遍清空。如果数组比较大可以用一个vectorvectorint children(N1)的方式在每组数据里重新定义避免手动清空的麻烦。总之“全局变量多组数据”的组合一定要谨慎这是OJ比赛里非常经典的失分点。6. 从L2—051延伸开去的备赛思路6.1 把这道题抽象成一套树模板做完这道题我强烈建议你把代码整理成自己的模板库。疫情也好比赛也罢真正做到考场上现想代码是不现实的尤其是L2题拼的就是你模板熟不熟。从“满树的遍历”可以抽象出几个非常通用的模块建树模块、找根模块、BFS层序模块、DFS先序/后序模块、性质判断模块。这五个模块可以自由组合套用到天梯赛大量树相关题目里。比如“树的同构”那道题本质上就是建树、找根、递归比较三个模块的拼接“根据后序和中序输出先序”那道题就是建树模块的变种只不过孩子信息不是直接给的而是从遍历序列里推算出来的。如果你能把L2—051这套模板吃透面对大多数L2树题都会有一种“这道题我拆过”的感觉。6.2 我个人的一点备赛心得我刷天梯赛真题的经验是L2部分不要追求做多要追求做精。每道题做完之后抽出十分钟把这道题考的数据结构知识点、边界条件、坑点记在笔记里。比如“满树的遍历”这道题我记下的关键词就是“vector建树”“hasFather找根”“全局标记防提前退出”。等到比赛前一周翻笔记比重新刷题效率高得多。还有一个小建议每次训练都模拟比赛的输入输出方式不要在IDE里人肉输入样例调试直接写重定向或者写文件读入。养成这个习惯之后正式比赛时你会少很多紧张感因为流程已经变成肌肉记忆了。天梯赛的分数差距往往不大很多时候决定拿不拿奖的就是L2这部分的稳定输出而稳定输出来源于平时对这些基础模板题的大量复盘。希望这篇题解能帮你把“满树的遍历”稳稳吃透L2再遇到树的题目时能多一分从容。