PTA天梯赛的L2-011“玩转二叉树”我印象太深了。这题表面上是让你“玩”二叉树实际把二叉树遍历、递归建树、树的镜像反转、层序遍历四个考点一次性全考了。很多同学L2卡住就是卡在这一题上单独拎出每个知识点都懂一合起来就不知道代码从哪下笔。今天就把这道题从题目拆解到完整代码再到我踩过的坑全部捋一遍。准备天梯赛、考研机试、校招笔试的同学这题的思路值得你花一个晚上彻底吃透。先说结论这题的核心只有一句话——用中序遍历前序遍历还原二叉树结构然后把每个节点的左右子树互换最后按层输出节点值。听起来简单但里面的递归边界、反转时机、层序输出格式全是细节。下面我按自己的理解一步步拆开讲。1. 题目到底在考什么先拆解再动手1.1 四合一考点一个都不少先看看这题的显性要求给一棵二叉树的中序遍历序列和前序遍历序列要求输出“镜面反转”后的层序遍历序列。这句话翻译成人话就是四步根据中序前序恢复出原始的二叉树结构。把树做镜面反转也就是每个节点的左右子树互换。对反转后的树做层序遍历BFS。在一行里输出结果数字间一个空格行首行尾都不能有空格。考点拆开看都不难但合在一起对递归理解和代码组织能力是个不小的考验。尤其是第一步“建树”这题的核心难点全在这。树建对了后面三步都是模板级操作。1.2 为什么“中序前序”能唯一确定一棵二叉树经常有同学问为什么中序前序能确定唯一的树而前序后序不行前序遍历的顺序是“根节点→左子树→右子树”所以前序序列的第一个元素一定是整棵树的根。但光知道根还不够我们不知道左子树有哪些节点、右子树有哪些节点这时候中序遍历就派上用场了。中序遍历的顺序是“左子树→根节点→右子树”。既然前序已经告诉了我们根是谁我们就能在中序序列里找到这个根的位置。中序序列中根的左边全是左子树的节点右边全是右子树的节点。于是整棵树被分成了左右两半再对每一半递归做同样的操作就能还原出整棵树。为什么前序后序不行因为前序和后序都是先访问左右子树中的某一个再访问另一个但无法区分哪些节点属于左子树、哪些属于右子树。举个最简单的例子一棵只有左孩子的二叉树“1→2”和前序“1 2”、后序“2 1”能匹配一棵只有右孩子的二叉树“1→2”前序还是“1 2”后序还是“2 1”。你看两种完全不同的树给出的两个遍历序列一模一样自然无法唯一确定。所以中序必配前序或后序这是建树类题目的基础逻辑。理解了这个L2-011的建树部分就不难了。1.3 镜像反转到底是反什么题目里的“镜面反转”其实就是把二叉树的每一个节点都做一次左右孩子交换效果相当于对着镜子照了一下左右颠倒。这一步和LeetCode 226“翻转二叉树”是同一个操作。递归写起来极其简单先交换当前节点的左右孩子再递归交换左子树和右子树。但有个容易忽略的问题如果你在建树的过程中顺便交换或者先交换再层序输出结果会不一样。这题要求的是“原树反转后的层序”做题时一定要想清楚反转发生在哪个时间点后面我会专门讲这个坑。2. 核心细节与实现要点2.1 递归建树时区间边界怎么算不出错建树递归函数我习惯这样定义Node* build(int preL, int preR, int inL, int inR);四个参数分别表示当前子树在前序序列中的区间[preL, preR]以及在中序序列中的区间[inL, inR]。每次递归前序区间的第一个元素pre[preL]就是当前子树的根节点值。然后我们在中序区间里找到这个值的位置k于是左子树的节点个数numLeft k - inL左子树的中序区间[inL, k-1]右子树的中序区间[k1, inR]左子树的前序区间[preL1, preLnumLeft]右子树的前序区间[preLnumLeft1, preR]这五个式子是整个建树过程的核心建议直接背下来。我见过很多同学在preLnumLeft还是preLnumLeft1上反复纠结其实只要搞清楚一个原则前序序列中紧跟着根节点的那一段连续区间就是左子树的前序序列长度和中序里左子树的长度一定相等。用这个原则去推导永远不会错。递归终止条件是preL preR这时左子树或右子树为空返回NULL。2.2 找根节点在中序中的位置用什么方法N≤30理论上每次递归都遍历一遍中序区间也能过。但如果题目数据量变大这种做法就会退化到O(N²)。我在写这题时习惯直接用unordered_map记录每个值在中序序列中的下标这样在建树时能用O(1)时间找到根的位置整体复杂度降到O(N)。不过要注意题目里节点的键值是“互不相等的正整数”所以用map或unordered_map都没问题。如果键值可能出现重复那这种建树方式就不成立了你得换用其它方法。但竞赛题一般都会保证互不相等所以可以放心用。2.3 层序遍历输出为什么要用队列层序遍历就是按从上到下、从左到右的顺序访问节点天然适合用BFS实现。BFS的标准结构是队列根节点入队。队首出队访问它。如果它有左孩子左孩子入队。如果它有右孩子右孩子入队。重复2~4直到队列为空。为什么用队列而不是栈因为队列是先进先出能保证同一层的节点按从左到右的顺序被处理。如果换成栈就会变成深度优先的“先往深处走”层序就乱了。输出格式上也有一点小讲究这题要求“数字间以1个空格分隔行末不得有多余空格”。最简单的处理是用一个变量记录已经输出了多少个节点第一个直接打印后面的先打印一个空格再打印数字。千万别在节点后面统一加空格否则行末会多一个被判格式错误。3. 完整代码与逐步拆解3.1 数据结构数组模拟二叉树用指针建树当然可以但我更推荐用结构体数组代码更短也避免了指针操作的各种细节问题。节点定义很简单struct Node { int l, r; } tree[40];数组下标就是节点编号也就是节点值tree[val].l存左孩子值没有则为0tree[val].r存右孩子值。题目说键值是正整数N≤30所以值最大不会超过N用数组下标存非常安全。3.2 建树函数递归的核心函数的参数和前面说的一致。代码我写成这样#include bits/stdc.h using namespace std; const int MAXN 40; int pre[MAXN], in[MAXN]; int n; unordered_mapint, int pos; struct Node { int l, r; } tree[MAXN]; // 根据前序区间和中序区间建树 void build(int preL, int preR, int inL, int inR) { int root pre[preL]; // 前序第一个是根 int k pos[root]; // 根在中序中的位置 int numLeft k - inL; // 左子树节点个数 // 如果左子树非空递归建立左子树 if (numLeft 0) { tree[root].l pre[preL 1]; build(preL 1, preL numLeft, inL, k - 1); } // 如果右子树非空递归建立右子树 if (preL numLeft 1 preR) { tree[root].r pre[preL numLeft 1]; build(preL numLeft 1, preR, k 1, inR); } }这里我把tree[root].l和tree[root].r的赋值放在递归之前效果上没问题。更严谨的写法是先递归返回孩子节点再赋值但在数组实现里只要递归前明确当前根的孩子就是对应区间的第一个元素直接赋值是安全的。3.3 镜像反转递归交换左右孩子反转的递归写法很简单void invert(int root) { if (root 0) return; swap(tree[root].l, tree[root].r); invert(tree[root].l); invert(tree[root].r); }注意顺序先交换当前节点的左右孩子再递归处理左子树此时原来的右子树和右子树此时原来的左子树。这种写法等价于先交换、后递归逻辑上最清晰。这里有个细节很多同学会写错swap之后tree[root].l指向的是原来的右孩子tree[root].r指向的是原来的左孩子。所以交换完成后递归调用一定是invert(tree[root].l)和invert(tree[root].r)而不是去递归原来的左右子树。当然你按原始左右子树记录下来再递归也一样但swap后再递归更简洁。3.4 层序遍历队列模板层序遍历用queueint实现void levelOrder(int root) { queueint q; q.push(root); int cnt 0; while (!q.empty()) { int now q.front(); q.pop(); cnt; if (cnt 1) cout now; else cout now; if (tree[now].l ! 0) q.push(tree[now].l); if (tree[now].r ! 0) q.push(tree[now].r); } }这里的cnt用来控制空格第一次输出直接输出节点值后面每个节点前加一个空格完美满足“行末不得有多余空格”的要求。3.5 完整可运行代码把上面的拼在一起#include bits/stdc.h using namespace std; const int MAXN 40; int pre[MAXN], in[MAXN]; int n; unordered_mapint, int pos; struct Node { int l, r; } tree[MAXN]; void build(int preL, int preR, int inL, int inR) { int root pre[preL]; int k pos[root]; int numLeft k - inL; if (numLeft 0) { tree[root].l pre[preL 1]; build(preL 1, preL numLeft, inL, k - 1); } if (preL numLeft 1 preR) { tree[root].r pre[preL numLeft 1]; build(preL numLeft 1, preR, k 1, inR); } } void invert(int root) { if (root 0) return; swap(tree[root].l, tree[root].r); invert(tree[root].l); invert(tree[root].r); } void levelOrder(int root) { queueint q; q.push(root); int cnt 0; while (!q.empty()) { int now q.front(); q.pop(); cnt; if (cnt 1) cout now; else cout now; if (tree[now].l ! 0) q.push(tree[now].l); if (tree[now].r ! 0) q.push(tree[now].r); } } int main() { cin n; for (int i 1; i n; i) { cin in[i]; pos[in[i]] i; } for (int i 1; i n; i) { cin pre[i]; } build(1, n, 1, n); int root pre[1]; invert(root); levelOrder(root); return 0; }代码里我额外用unordered_map记录了中序序列每个值的位置这样build里找根位置的时间是常数级别。题目本身N≤30直接写个循环遍历也不会超时但养成用哈希表的习惯以后再遇到N10⁵的题目也能直接套同一套模板。3.6 样例运行验证用题目样例手算验证一下。输入7 1 2 3 4 5 6 7 4 1 3 2 6 5 7第一步前序第一个是4所以根是4。在中序里4的位置把序列分成左子树1 2 3和右子树5 6 7。第二步递归左子树前序是1 3 2中序是1 2 3。1是左子树的根中序里1在最左边说明1没有左孩子右子树是2 3。再递归前序3 2中序2 33是根2是3的左孩子。第三步递归右子树前序6 5 7中序5 6 7。6是根5是左孩子7是右孩子。原树的结构就是4 / \ 1 6 \ / \ 3 5 7 / 2层序是4 1 6 3 5 7 2。反转后4 / \ 6 1 / \ / \ 7 5 3 \ 2反转后的层序是4 6 1 7 5 3 2。这组数据下程序输出应该就是这一串。4. 常见问题与排查技巧实录4.1 递归区间算错导致建树“串位”这是最常见的错误。我见过不少同学把左子树的前序右边界写成preL numLeft右子树左边界写成preL numLeft 1结果递归到下面几层时左右子树的区间互相重叠树建得乱七八糟。排查方法很简单如果层序输出里出现了原序列中没有的重复值或者有些节点消失了八成是区间边界错了。建议在build函数开头打印一下当前的preL, preR, inL, inR用一个小样例手动走一遍很快就能定位。4.2 反转的时机不对有的人会把反转写进建树里一边建一边交换左右孩子赋值比如建左子树时把根放到右孩子位置。这会导致什么结果呢建出来的树左右结构是对的但如果你后面还要做其它操作比如输出原树的中序遍历、求原树的深度结果就全错了。这道题只要求输出反转后的层序所以“边建边反转”能过。但一旦题目变成“先输出原树中序再输出反转后层序”这种写法就会出错。更稳妥的做法是老老实实按原序建树建完之后再单独跑一次invert。这样代码的职责清晰后面想怎么扩展都方便。4.3 层序输出时忘了判空在levelOrder里入队前一定要判断左右孩子是否存在if (tree[now].l ! 0) q.push(tree[now].l); if (tree[now].r ! 0) q.push(tree[now].r);如果不判空0会被当成合法节点入队然后访问到tree[0]的左右孩子轻则多输出东西重则死循环。因为tree[0]的左右孩子初始化为0每次循环都把它加进队列永远出不完。这个问题在指针实现里更隐蔽因为空指针是NULL你可能会写if (node-left ! NULL)其实效果一样。总之判空不能省。4.4 用cin读入遇到行末多余空格题目给的是“数字间以空格分隔”所以用cin或scanf直接连续读入即可不需要处理换行。有些同学会纠结第二行、第三行末尾有没有空格其实cin会自动跳过空白字符完全不用担心。但输出端一定要自己控制好空格这是判题系统最容易挑刺的地方。4.5 数组越界问题我的代码用节点值作为数组下标题目保证值在正整数范围内且N≤30所以数组开40就够。但如果你改用了结构体指针建树记得每个新节点都要new并且判断是否为空。指针版本调试起来比数组版本麻烦建议平时练习时两种都写一遍比赛时用自己最熟练的一种。4.6 建树失败却没报错有时候递归区间算错但程序不会报错只是输出结果不对。这时候会很难排查。我的经验是先别急着调层序输出先写一个临时函数输出反转前的中序遍历或前序遍历和题目给的输入比对。如果中间结果能对上说明建树正确问题出在反转或者层序如果中间结果已经乱了说明建树区间有问题。这样能快速缩小范围。5. 从这题延伸出去一套模板通吃遍历题5.1 中序后序建树代码只改三行L2里还有一道常见的题是给中序后序要求输出层序或前序。思路和中序前序完全对称只是根节点要从后序序列的最后一个元素取。对应的建树函数改成void buildPost(int postL, int postR, int inL, int inR) { int root post[postR]; // 后序最后一个是根 int k pos[root]; int numLeft k - inL; if (numLeft 0) { tree[root].l post[postL numLeft - 1]; buildPost(postL, postL numLeft - 1, inL, k - 1); } if (postL numLeft postR - 1) { tree[root].r post[postR - 1]; buildPost(postL numLeft, postR - 1, k 1, inR); } }你会发现核心思想永远是先找根再切左右区间然后递归。掌握了这个套路不管题目给的是前序、后序还是层序只要搭配一个中序你都能建树。5.2 中序层序建树另一种玩法有些题目会给出层序遍历序列和中序遍历序列让你建树。思路是层序序列中第一个出现的节点一定是整棵树的根。然后在中序里找到根把层序序列剩下节点分成属于左子树和属于右子树的两组注意要保持它们在层序里的相对顺序分别递归建树。这类题比L2-011稍微绕一点但本质上还是“用一个遍历找根用另一个遍历划分左右子树”的经典套路。我建议大家把前序中序、后序中序、层序中序三种组合都练一遍建树这关就算彻底过了。5.3 和二叉树的深度、搜索二叉树的关系做完这题可以顺手扩展一下在已经建好的树上求二叉树的深度也就是从根到最远叶子节点的距离。递归三行就能写int getDepth(int root) { if (root 0) return 0; return max(getDepth(tree[root].l), getDepth(tree[root].r)) 1; }如果是搜索二叉树BST性质更特殊中序遍历序列一定是递增的。所以很多搜索二叉树的题目只需要给你一个前序或后序再借助“中序有序”这个条件就能建树连中序输入都省了。理解L2-011的划分逻辑后再看BST的这类题目会轻松很多。5.4 我的一点做题体会这题我在不同阶段写过三遍。第一遍照着题解抄抄完似懂非懂第二遍自己从头写区间边界错了两次靠打印调试才改对第三遍是在准备机试时要求自己十分钟内无脑AC写到这里才真正理解每一步为什么这么写。我个人的建议是别满足于AC做完之后把几种遍历组合的建树都写一遍再想想如果N变成十万、键值范围变大你的代码要改哪些地方。这样一道题就能顶三道题。最后再分享一个小技巧每次写递归建树前先在草稿纸上画出区间划分的示意图把preL, preR, inL, inR标上去再写代码。我后来做题速度提升靠的就是这个习惯。L2-011这个“玩转二叉树”玩明白了后面很多树相关的题都会顺手很多。