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] - 右子树的中序区间：
[k+1, inR] - 左子树的前序区间：
[preL+1, preL+numLeft] - 右子树的前序区间：
[preL+numLeft+1, preR]
这五个式子是整个建树过程的核心，建议直接背下来。我见过很多同学在preL+numLeft还是preL+numLeft+1上反复纠结，其实只要搞清楚一个原则：前序序列中，紧跟着根节点的那一段连续区间，就是左子树的前序序列，长度和中序里左子树的长度一定相等。用这个原则去推导，永远不会错。
递归终止条件是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存左孩子值（没有则为0），tree[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_map<int, 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 层序遍历：队列模板
层序遍历用queue<int>实现：
void levelOrder(int root) { queue<int> 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_map<int, 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) { queue<int> 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，直接写个循环遍历也不会超时，但养成用哈希表的习惯，以后再遇到N=10⁵的题目也能直接套同一套模板。
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 3，3是根，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这个“玩转二叉树”，玩明白了，后面很多树相关的题都会顺手很多。
)
