做PTA天梯赛刷题的朋友应该对L2-011《玩转二叉树》不陌生。我每次带学生刷到这里都会说一句话：这道题名字看着轻松，实际上是把“遍历还原二叉树”“镜像反转”“层序遍历”三个硬知识点串成了一条链，任何一环掉了链子，输出就是错的。题面也很有意思——它不要求你输出原来的层序，而是要求输出“镜面反转后”的层序，也就是把所有非叶节点的左右孩子对调之后再按层输出。这一下就难住了不少习惯只背模板的人。
这篇文章我会从题目本质拆起，把前序+中序为什么能唯一确定一棵二叉树讲透，再给出递归建树的完整推演和代码，顺便聊一个很巧的偷懒技巧：镜像反转根本不需要真的翻转树，BFS时把入队顺序换成先右后左就行。最后补上我自己刷这题时踩过的坑和几个必测的边界样例。文章适合刚学完二叉树遍历、准备冲天梯赛L2的选手，也适合想加深对递归理解的同学。
1. 这道题的真正考点：三件事串成一条线
1.1 题目到底要你干什么
先把题面用大白话翻译一遍。
输入两行序列，第一行是中序遍历结果，第二行是前序遍历结果，节点个数N不超过30，键值互不相同。要求输出这个二叉树在“完全镜像反转”之后（每个节点的左右孩子全部对调）的层序遍历结果。
这里有个容易懵的地方：题目说的“镜面反转”不是让你画一棵新树，而是让你在原树基础上做一次全局的孩子对调。比如根节点的左子树整体挪到右边，右子树整体挪到左边，对每个子节点也要递归地做同样的交换，最后输出这棵新树的层序。
所以这道题真正考察的是三个递进的能力：
- 能不能从前序+中序遍历还原出一棵二叉树；
- 能不能对树结构做镜像操作；
- 能不能正确完成层序遍历的输出。
单独拿出来每一项都不难，但组合在一起，就特别容易在“还原”这一步出错，然后一错全错。
1.2 为什么前序确定根、中序切左右，组合起来能唯一还原一棵树
先复习一条基本性质：前序遍历的顺序是“根左右”，中序遍历的顺序是“左根右”。
这句话看起来人人都知道，但很多人没有真正理解它的威力。前序遍历序列的第一个元素，一定是整棵树的根节点。而中序遍历序列里，根节点左边的所有节点属于左子树，右边的所有节点属于右子树。
有了这两个信息，你就能把一棵树劈成三块：根节点、左子树的中序序列、右子树的中序序列。那左子树的前序序列呢？也很简单，从左子树的中序序列长度就能推导出来。
这就像拼拼图时先找到一块最特殊的拼图当作定位点，然后根据它的位置把剩余拼图划成左半区和右半区。前序负责告诉你“哪一块是定位点”，中序负责告诉你“定位点周围怎么分”。两个信息缺一不可，而且组合起来之后可以不断递归，直到拼出整棵树。
1.3 N≤30不是给你偷懒的理由，而是考察方向的提示
第一次看到N≤30这个数据范围，很多人会想：这么小，随便暴力就行。
这话对了一半。N很小确实意味着你不需要对性能做极限优化，但它的真正含义是：出题人希望你把精力放在“建树逻辑”本身，而不是放在常数优化上。换句话说，这道题是典型的算法教学题，考察的是你对递归和遍历关系的理解是否透彻，而不是考察你是否会写线段树或哈希表加速。
所以刷这道题时应该关注的是：递归函数怎么设计、区间边界怎么算、空子树怎么处理。这些才是真正的得分点。等你把这些想明白了，就会发现N=30和N=100000在建树逻辑上完全一样，只是时间常数的问题。
2. 递归建树：从手工推演到区间公式
2.1 拿一组数据手动走一遍
光说原理不如亲手推一遍。假设输入是这样的：
中序：1 2 3 4 5 6 7 前序：4 2 1 3 6 5 7
第一步，看前序的第一个元素4，这就是整棵树的根。然后回到中序序列里找4的位置，发现它在第四个位置，于是左子树的中序是1 2 3，右子树的中序是5 6 7。左子树长度是3。
第二步，既然左子树长度为3，那么前序序列从第二个元素开始的3个元素就是左子树的前序：2 1 3。剩下的6 5 7就是右子树的前序。
第三步，递归处理左子树。前序2 1 3的第一个元素2是左子树的根，在中序1 2 3里找到2，得到左子树的左子树中序1，右子树中序3。前序剩余部分1 3，长度为1的1是左孩子的前序，3是右孩子的前序。
继续递归下去，右子树也是同理，根是6，左边是5，右边是7。
最终还原出来的树长得非常规整：
4 / \ 2 6 / \ / \ 1 3 5 7普通层序遍历是：4 2 6 1 3 5 7。但这题要的是镜像反转后的层序，也就是先在每层从右往左看，结果是：4 6 2 7 5 3 1。先记下这个结果，后面验证代码时要用。
2.2 区间公式的几何直觉：四个下标是怎么算出来的
手工推演很直观，但写代码时要把推演过程转化成递归函数的区间参数。很多人在这一步翻车，主要是四个下标绕晕了。我习惯用这样的方式来理解。
假设当前递归处理的是中序区间[inL, inR]和前序区间[preL, preR]。前序的第一个元素pre[preL]是根，需要在中序区间里找到根的位置。设这个位置是k。
根把中序区间分成了两半：
- 左子树中序区间：[inL, k - 1]
- 右子树中序区间：[k + 1, inR]
- 左子树长度：leftLen = k - inL
有了左子树长度，就能切分前序区间。前序的结构是“根 + 整棵左子树的前序 + 整棵右子树的前序”，所以：
- 左子树前序区间：[preL + 1, preL + leftLen]
- 右子树前序区间：[preL + leftLen + 1, preR]
把这个看成“先扣掉根，再把剩余部分按左子树长度切成两段”就可以了。
为了防止背错，我自己有一个记忆技巧：左边界的计算，永远是从preL出发往右偏移；右边界则用左边界加上长度再减一。递归结束条件是preL > preR，代表前序区间为空，也就是空子树，直接返回-1。
2.3 工程写法：用数组模拟二叉树，不碰指针
刷题时我强烈推荐用数组模拟二叉树，而不是去new一个TreeNode。原因有两点：一是避免手动管理内存，二是调试时直接打印数组下标更直观。
具体做法是定义一个结构体数组：
const int MAXN = 35; int in[MAXN], pre[MAXN]; struct Node { int val; int left, right; } tree[MAXN]; int nodeCnt = 0;build函数返回的是该节点在tree数组中的下标，不是节点值。这个设计能让后面BFS时直接用下标访问左右孩子，非常舒服。
int build(int preL, int preR, int inL, int inR) { if (preL > preR) return -1; int rootIdx = nodeCnt++; tree[rootIdx].val = pre[preL]; int k = inL; while (in[k] != tree[rootIdx].val) k++; int leftLen = k - inL; tree[rootIdx].left = build(preL + 1, preL + leftLen, inL, k - 1); tree[rootIdx].right = build(preL + leftLen + 1, preR, k + 1, inR); return rootIdx; }这个代码的优点是：tree数组的下标是节点编号，跟键值无关，所以无论键值多大都不会越界。left和right存的是子节点的下标，递归边界返回-1表示不存在。
3. 镜像反转的两种做法，以及为什么能偷懒
3.1 最直观的做法：真的把树翻转一遍
如果你第一时间想到的是“先把树翻转，再层序遍历”，这个思路完全没问题。
在建树完成之后，写一个递归函数交换每个节点的左右孩子：
void mirror(int idx) { if (idx == -1) return; mirror(tree[idx].left); mirror(tree[idx].right); swap(tree[idx].left, tree[idx].right); }然后把exchange后的树做普通BFS层序遍历输出。这样做逻辑清晰，写完也容易验证，缺点是多了一次递归遍历的开销。但别忘了N≤30，这点开销完全可以忽略。
我之所以不首推这种写法，是因为它多了一步操作，而竞赛场上少一步操作就少一个犯错的机会。后面这种写法，一行改动就能达到同样的效果。
3.2 一行改动偷天换日：BFS时先右后左
答案的核心技巧就在这里：普通层序BFS是出队时先推左孩子再推右孩子，而镜像反转后的层序，只需要把这个顺序反过来，先推右孩子再推左孩子。
void levelOrderOnMirrorTree(int root) { if (root == -1) return; queue<int> q; q.push(root); bool first = true; while (!q.empty()) { int idx = q.front(); q.pop(); if (!first) cout << " "; first = false; cout << tree[idx].val; if (tree[idx].right != -1) q.push(tree[idx].right); if (tree[idx].left != -1) q.push(tree[idx].left); } }对，就这么简单。不需要额外翻转，不需要新树，不需要递归。输出顺序从“先左后右”改成“先右后左”，结果直接就是镜像树的层序。
用刚才那个完全二叉树的例子验证：根4入队，出队时先推右孩子6再推左孩子2，队列变[6, 2]；出6推7和5，出2推3和1，最终输出的序列是4 6 2 7 5 3 1，跟手工推演完全一致。
3.3 严格论证：为什么“先右后左”等价于“翻转后的层序”
这里值得多说一句为什么能这样偷懒，因为它不是巧合，而是层序遍历和镜像操作之间的一个对称性质。
层序遍历的本质是按“层”从上到下输出，每一层内部按从左到右的顺序。镜像反转的本质是交换所有节点的左右孩子，这会导致每一层内部的节点顺序整体反过来。但是层与层之间的先后关系不变，上一层永远在下一层之前输出。
所以镜面树的层序遍历，等于原树按照“每层内部从右到左”的顺序遍历。而BFS队列天然是以“层”为单位推进的，只要在扩展某个节点时，先让右孩子入队、再让左孩子入队，队列后续的弹出顺序就会自动变成“同层从右到左”。递归地看，这个性质对每一层都成立，因此两者完全等价。
如果还不放心，可以再拿一个更一般的例子：
中序：1 2 3 4 5 前序：3 1 2 4 5
这棵树长得并不对称：
3 / \ 1 4 \ \ 2 5普通层序是3 1 4 2 5。镜像反转后的树长这样：
3 / \ 4 1 / / 5 2镜像树层序是3 4 1 5 2。而直接在原树上按“先右后左”BFS，输出同样是3 4 1 5 2。两次结果完全一致，这说明技巧是可靠的。
4. 提交前必须焊死的五个边界条件
4.1 空子树返回约定：-1必须贯穿始终
写build函数时，递归终止条件是preL > preR，返回-1。这里的关键是“约定必须一致”：初始化tree数组时left和right要设为-1，BFS判断孩子是否存在时也要用-1来判断。如果你初始化时用了0，那么下标为0的节点就会被误判成空指针。
一个典型的错误是把结构体数组初始化为全0，结果build返回-1之后，数组里还残留着之前的值，或者BFS里写if (tree[idx].left)这种判断，把下标为0的节点漏掉。我建议统一用-1表示空，并且写一段初始化代码把left和right全部置为-1。
for (int i = 0; i < MAXN; i++) { tree[i].left = -1; tree[i].right = -1; }4.2 值域陷阱：键值不能直接当下标
题目只说了键值互不相等，但没说值域是1到N。如果键值很大，比如1000000000，你拿它直接当数组下标去开left和right数组，程序直接数组越界异常。
正确做法有两种。第一种就是我上面写的结构体数组版，节点用动态编号，跟键值解耦；第二种是先用unordered_map把键值映射到1到N的下标，再建树。在竞赛题里，第一种更简单直接，不容易引入额外数据结构错误。
4.3 输入顺序：先中序再前序，不是先前序
这是最冤枉的扣分点之一。题面明确写了：第二行是中序遍历，第三行是前序遍历。但很多人刷惯了其他题，一看到前序就习惯性地把第一行先读进pre数组，结果整棵树建反了还不自知。
我的建议是读入时做好注释，养成肌肉记忆：
for (int i = 0; i < n; i++) cin >> in[i]; for (int i = 0; i < n; i++) cin >> pre[i];顺序反了之后，程序不会报错，但输出结果会错得莫名其妙，而且这种错误极难定位，因为你盯着代码看半天也看不出逻辑问题。
4.4 自测样例：左右斜树、单节点、完全二叉树
N=1时，中序和前序都是同一个数，镜像反转后还是同一个数。这个测试用例最容易忽略，也最容易暴露边界问题。
两个方向相反的斜树也很适合自测。比如前序1 2 3，中序3 2 1表示一棵一直往左的树，镜像反转后会变成一直往右的树，但层序输出依然是1 2 3。这是因为斜着长的树，无论左右怎么翻转，每一层都只有一个节点。
我建议写完代码后用下面三组数据做自测：
- N=1：
in: 1, pre: 1→ 输出1 - 完全二叉树：中序1 2 3 4 5 6 7，前序4 2 1 3 6 5 7 → 输出
4 6 2 7 5 3 1 - 非对称树：中序1 2 3 4 5，前序3 1 2 4 5 → 输出
3 4 1 5 2
三个样例全部通过，基本可以放心提交。
4.5 输出格式：行首行尾不允许多余空格
这个细节可能丢失1到2分。错误做法是每次都输出空格然后换行，行尾会多一个空格。正确做法有两种：用first变量标记，或者把输出存进数组最后统一打印。
我在代码里用的是first变量法，这个模式在PTA系列题目里反复出现，背下来不亏。
5. 从一道真题看遍历家族的隐藏关系
5.1 层序遍历天然携带深度信息
热搜词里有“二叉树的深度”，顺便说一嘴。层序遍历有一个很实用的特性：每一轮队列中元素的数量就是当前层的宽度，所以只要在BFS时按层计数，就能顺手求出树的深度和每层节点个数。
如果你想在本题基础上额外输出深度，只需要在BFS循环里加一层处理：
int depth = 0; while (!q.empty()) { int levelSize = q.size(); depth++; while (levelSize--) { int idx = q.front(); q.pop(); // 处理节点 if (tree[idx].right != -1) q.push(tree[idx].right); if (tree[idx].left != -1) q.push(tree[idx].left); } }这个技能在L2系列很多题目里都用得上，层序求深度比递归求深度更贴近输出需求。
5.2 变体：层序+中序怎么重建？没有前序也不慌
不少读者刷完这题会好奇：如果给的是层序和中序，能不能重建？能，但比前序+中序要绕一点。
层序序列的第一个元素就是根，这没问题。问题在于，你不能像前序那样直接把层序序列按长度分成左右两段。因为层序遍历是跨左右子树交替出现的，左子树和右子树的节点在整个层序序列里是交错排列的。
正确做法是在递归过程中，给定当前子树的中序区间，然后去原始层序序列里“过滤”出属于这个区间的节点，保持它们在层序中的相对顺序，再把这些节点作为当前层的顺序，递归处理。思路不复杂，但写起来要注意过滤的代价，每次递归都要扫描一次层序序列，总的复杂度会到O(n²)。对于N只有几十的题，完全够用。
5.3 为什么搜索二叉树（BST）可以省略中序输入
如果你遇到一棵搜索二叉树（BST），它的中序遍历结果一定是升序的。这是一个非常重要的性质，因为这意味着你根本不需要题目给中序序列——只要把前序（或层序）里的节点排个序，就等于拿到了中序。
更妙的是，BST还有一个性质：前序序列里，第一个节点是根，比根小的节点全在左子树，比根大的全在右子树。所以你甚至不需要中序序列，就能用前序直接完成建树。具体做法是：以根节点为界，把前序剩余部分分成小于根和大于根两段，递归建树。这个思路在很多BST相关题目里非常高效。
不过回到L2-011这道题，它给的是普通二叉树，没有BST这个性质，所以中序序列必须显式给出。这也是出题人的用心之处：让你老老实实掌握通用建树方法，而不是靠取巧。
5.4 复杂度审视：O(n²)为什么在N≤30下完全不是问题
最后聊聊复杂度。build函数每次都要在中序区间内线性扫描找根的位置，最坏情况下每次扫描的长度接近n，递归一共处理n个节点，所以总复杂度是O(n²)。
很多人一看到O(n²)就想优化，但实际上N≤30时，哪怕n²也只有900次操作，在计算机看来完全是瞬时完成。就算N放大到1000，O(n²)也只有100万次操作，依然没有压力。真正需要优化的场景是n达到10万以上，那时候可以用哈希表存储“键值→中序下标”的映射，把查找根节点的过程降到O(1)，建树总复杂度变成O(n)。
把这层关系想明白，你就不会在L2-011上浪费时间去写复杂的哈希映射，而是把时间花在真正容易出错的地方。等将来遇到N很大的同类题时，再升级方案也来得及。
我在实际刷题过程中，第一版总是先用最简单的方式跑通逻辑，再考虑优化。因为竞赛里最怕的不是复杂度高，而是“写了半天还没跑通”。L2-011就是这样一道典型题目：思路清晰、边界明确，只要把递归区间和镜像输出顺序搞明白，拿满分是非常轻松的事。
