先说我第一次做 L2-011 时的感受题目看着不长样例也好懂可真正动手写的时候卡在了“后序中序怎么还原二叉树”这个环节区间边界错了好几轮最后输出全是乱序。后来刷多了这类题才发现L2-011 考的根本不是“会不会二叉树”而是“你知不知道怎么从遍历序列里把一棵树捞回来”。二叉树相关的基本功比如二叉树的深度、二叉树的遍历、搜索二叉树的特性全都浓缩在这一道题里。这道题适合谁适合刚学完树结构、准备参加天梯赛或刷 PTA 的同学也适合那些会写递归但一遇到区间划分就头晕的“半熟手”。题目本身不涉及复杂算法却能帮你把递归建树、层序遍历、左右子树交换这些操作一次练到位。这篇文章我不光会给出可提交的代码还会把每一步的推导、边界设计和常见坑全部摊开来讲清楚争取让你看完之后能独立手写一遍而不是只会复制粘贴。1. 拿到 L2-011 之前先聊聊二叉树到底在考什么1.1 题目到底让你做什么L2-011 的原题给定了两样东西一棵二叉树的中序遍历序列和后序遍历序列。要求是你把这棵二叉树还原出来然后“玩转”它——所谓玩转其实就是要你输出这棵树经过左右子树互换之后的层序遍历结果。这里有一个很关键的信息只靠中序后序就能唯一确定一棵二叉树。很多人第一反应是“我能不能用前序后序”不行。前序后序只能确定父子关系无法区分左右子树还原结果不唯一。而中序配合前序或后序能明确地告诉你在根节点左边和右边分别有哪些节点这是唯一性的根基。题目的输入看起来很简单第一行是节点个数 N第二行是中序序列第三行是后序序列。但你别小看这道题它是天梯赛 L2 级别的入门题也是很多高校数据结构课的经典作业题。因为它的解法覆盖了二叉树递归建树、层序遍历、以及“镜像反转”三种核心操作一道题串起一整条知识点链。输出更是有意思它不要中序不要前序只要反转后的层序。这意味着即便你建出了一棵正确的树如果层序输出时队列的入队顺序写反了也会全盘皆输。所以这道题最容易出错的地方反而不是建树而是“你以为你镜像过了其实没有”。1.2 为什么“遍历”是二叉树的灵魂二叉树这个结构本身并不稀奇就是每个节点最多两个孩子的树。真正让二叉树变得有用的是围绕它的四种遍历方式前序遍历、中序遍历、后序遍历、层序遍历。四种遍历各有各的“记忆密码”而 L2-011 一口气用到了其中三种。我自己教学员时经常说一句话遍历不是打印顺序而是对树的“访问策略”。前序是“先访问根再去左再去右”中序是“先左再根再右”后序是“先左再右再根”。每一种策略都决定了你拿到序列后能得到什么样的信息量。比如中序序列有一个天然特征根节点的位置把序列劈成两半左半是左子树的中序右半是右子树的中序。而后序序列的特征是最后一个位置一定是整棵树的根。这两个特征加在一起就构成了还原二叉树的全部依据。很多人背下了定义做题却不会用原因就在于没有真正理解“遍历序列是树在某种访问策略下的投影”。我举个生活化例子如果说中序序列是一队人按照“左子树、根、右子树”的顺序报数那么后序就是同一队人按照“左子树、右子树、根”的顺序报数。你拿到两份报数名单就能通过根的位置反推每个人的站位。1.3 两套遍历序列如何确定一棵树还原树的过程就好比拼拼图。后序序列的最后一块必定是根这个没有任何商量余地。拿到根之后回到中序序列里找这个根的位置根左边那一串就是左子树的中序序列根右边那一串就是右子树的中序序列。接下来再回到后序序列里数出同样数量的区间左边是左子树的后序右边是右子树的后序。于是一个规模为 n 的问题被拆成了两个规模减半的子问题。递归思想在这里就体现出来了子问题依旧是一个“中序后序建树”的问题只是区间不同罢了。你不断重复“取后序末尾当根、在中序里定位、划分左右子树区间”的步骤直到区间为空。这个递归的边界条件就是中序区间左下角大于右下角代表当前子树没有节点了返回空指针即可。有一个细节值得强调划分后序区间时我们不是直接“看起来差不多”就切而是先计算左子树的节点数量也就是根在中序里的位置减去中序区间的左端点然后再用这个数量去后序区间里精确切分。这一步是整套代码里最容易出 bug 的地方也是我后面会重点拆解的环节。只要这里想明白了建树的递归也就通了。2. 建树的完整思路后序中序如何还原二叉树2.1 从一个例子手工推演我们拿题目的样例数据来走一遍完整流程请你把手头的纸笔拿出来跟着我一起画。中序序列是1 2 3 4 5 6 7后序序列是2 3 1 5 7 6 4。第一步看后序序列的最后一个元素是 4所以根节点就是 4。回到中序里找 4发现它在第 4 个位置从 1 开始数于是中序被切成[1 2 3]和[5 6 7]两段左边三个节点右边三个节点。第二步看左边这三个节点在中序里是1 2 3那么在后序里也一定对应前三个位置2 3 1。这棵子树的后序是2 3 1最后一个又是 1所以左子树的根是 1。回到左子树的中序里找 1它在最前面说明 1 没有左子树中序右边是2 3对应后序的2 3。于是 1 的右子树继续递归后序2 3最后一个根是 33 在中序里的左子树是2右子树为空。第三步看根 4 的右子树中序为5 6 7在后序里对应的就是后序的左起第 4 到第 6 位5 7 6。最后一个 6 是根中序里 6 左边是 5右边是 7所以 6 的左孩子是 5右孩子是 7。到这里原始二叉树就完整还原出来了根是 4左孩子是 1右孩子是 61 没有左孩子右孩子是 33 的左孩子是 26 的左孩子是 5右孩子是 7。你可以按这个结构画出原始树然后尝试把每个节点的左右子树互换再看看层序是不是题目输出的4 6 1 7 5 3 2。这里我给你留一个手动验证的技巧层序遍历就是“按层从左到右”访问镜像之后根还是 4第二层从左到右是 6 和 1第三层是 7 5 3最后是 2。如果你自己画出来跟这个顺序一致说明你前面的建树和镜像都做对了。2.2 递归函数怎么写区间划分是关键手动推演是一回事写成递归又是另一回事。我见过太多人笔试能推对代码却写不对问题几乎全出在递归函数的参数设计上。先定义清楚中序序列存放在in数组后序序列存放在post数组。递归函数的任务是处理某一棵子树这个子树在中序里的范围是[inL, inR]在后序里的范围是[postL, postR]。代码骨架如下Node* build(int inL, int inR, int postL, int postR) { if (inL inR) return nullptr; int rootVal post[postR]; Node* root new Node(rootVal); int pos inL; while (in[pos] ! rootVal) pos; int leftSize pos - inL; root-left build(inL, pos - 1, postL, postL leftSize - 1); root-right build(pos 1, inR, postL leftSize, postR - 1); return root; }其中最难理解的就是leftSize和后序区间。pos - inL算的是根节点在中序里左边有几个元素也就是左子树节点的数量。既然左子树有leftSize个节点那么在后序序列里从postL开始数leftSize个位置就是左子树的后序区间最后结束在postL leftSize - 1。剩下的部分也就是从postL leftSize到postR - 1自然就是右子树的后序区间。这里我踩过一个特别深的坑我曾把右子树的后序结束写成postR想着“反正是右子树嘛应该到末尾”。但别忘了当前子树的根post[postR]已经被切出去了右子树的后序区间必须往后刨掉一位否则递归下一层时会把当前根当成右子树的根树的结构直接错乱。算法思维要求我们精确到边界的每一位这也正是写这类递归最需要训练的地方。细节方面再补一句如果你选择的编程语言不支持传入多个区间参数也可以用全局数组加成员变量的写法。但 C 的结构体指针方式是最直观的标准写法后续层序遍历也顺手。2.3 如果你是小偷懒型选手直接建出镜像树有的同学会说“反正题目最后要的是镜像后的层序那我能不能在建树时直接把左右子树对调”当然可以而且这是一个完全合规、思路还特别清晰的偷懒方案。做法就是把build函数里两行赋值换一下原本是root-left build(左子树区间)、root-right build(右子树区间)现在改成root-left build(右子树区间)、root-right build(左子树区间)。这样一来建树过程本身就是建一棵镜像树省掉了后面单独的镜像操作。这个方案的优点是你只需要维护一个递归函数少写一个mirror函数出错概率也小。缺点是它有点“取巧”一旦题目改成“输出镜像后的中序序列”你可能又要重新推导。我的建议是你至少要能看懂两种方案如果考试时间紧直接用这个“建树时交换”的方案正确率高代码也更短。不过话说回来如果你是想实打实练基本功我还是推荐先正常建树再单独写一个交换函数。因为这道题的精髓就在于让你理解“一棵树怎么还原”“镜像是什么概念”两步分开写每一步都是独立的考点。3. 镜像反转与层序遍历的实现细节3.1 三种镜像方案哪一种适合你提到二叉树的镜像很多初学者第一反应是“把整棵树画出来左右对着翻”。这个理解没错但代码实现至少有三种手段我按推荐程度给你排个序。第一种是用递归交换每个节点的左右孩子这也是最“正统”的做法void mirror(Node* root) { if (!root) return; swap(root-left, root-right); mirror(root-left); mirror(root-right); }这个写法本质上是一个后序遍历先交换当前节点的左右孩子再递归处理左右子树。注意交换之后原来的右孩子变成了左孩子所以递归处理root-left等价于处理原来的右子树不会出现遗漏。逻辑非常干净建议优先掌握。第二种是我上面说过的“建树时交换”。它的本质是让递归函数在生成节点时就把左右子树的身份对调整个树的形态从一开始就是镜像的后面不需要任何额外操作。第三种是最隐蔽的也是我真的见过有人这么用的不建树、不交换只在层序遍历时改变入队顺序。因为层序遍历天然是“从某一层左边扫到右边”对于一棵以根节点为镜像轴翻转过的树其层序实际上就是把原来的“从左到右”改成“从右到左”。所以你在levelOrder函数里不先入队左孩子而是先入队右孩子再入队左孩子输出的结果就已经是镜像后的层序了。这个技巧在面试里特别讨喜因为代码改动量最小。但它有一个前提题目只要求输出镜像后的层序。如果还让你输出中序或者前序这个方法就不够用了。所以我给你的终极建议是三种方案都要能看懂考场上择优使用。3.2 层序遍历为什么用队列层序遍历的规则是逐层从左到右访问节点这个“先进先出”的过程天然对应队列这个数据结构。具体做法也很简单初始时把根节点放入队列然后进入循环每次从队头取出一个节点访问它的值再把它的左右孩子依次放入队尾。循环结束就是整棵树遍历完毕。我拆解一下队列状态帮助你理解假设树是4 6 1 7 5 3 2这棵镜像树开始队列是[4]。取 4输出入队 6 和 1队列变成[6, 1]。取 6输出入队 7 和 5队列变成[1, 7, 5]。取 1输出入队右孩子 3因为镜像后 1 没有左孩子队列变成[7, 5, 3]。取 7、5、3 输出最后 3 再入队 2队列清空。整个过程“取出谁、入队谁”都是确定的没有什么玄学。写代码的时候有一个很容易被忽略的点如果树为空N 为 0你要保证层序遍历函数不会访问空指针。一种稳妥的写法是函数入口处直接判断if (root nullptr) return;但在天梯赛数据里N 通常大于等于 1所以这一条在实际提交时不一定触发。不过养成空树判断的习惯总是好的毕竟你以后还要面对更多复杂的二叉树题。3.3 输出格式的坑空格与换行这道题的输出格式要求是在一行中输出层序遍历结果数字之间用空格分隔行末不能有多余空格。这听起来很简单但恰恰是很多人失分的重灾区。我见过一种比较糟糕的写法是每输出一个数字就打印一个空格最后行尾多了一个空格。PTA 的评测系统通常对行尾空格容忍度较高但这并不能成为你养成坏习惯的理由。更规范的做法是维护一个bool first标记只有第一个数字前不输出空格后续的每个数字前都输出一个空格。bool first true; while (!q.empty()) { Node* cur q.front(); q.pop(); if (!first) cout ; first false; cout cur-val; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } cout endl;这个写法已经成了我写输出格式的老套路不管题目要求的是数组输出、层序输出还是路径输出我都用这个标记法永不踩坑。如果你在一组输出里还要穿插其他信息也可以把层序结果先存进vector最后统一打印这样更灵活但代码会稍微长一点。考虑到这道题数据量不大vector方案完全没有性能问题怎么写都行关键是保持逻辑清晰。4. 完整可提交代码与调试经验4.1 C 完整代码下面这份是我在 PTA 上实际提交通过过的代码结构比较经典每一步都对应前文讲过的内容。建议你先自己憋着写一遍写不出来再看看完再默写一遍效果比你复制粘贴十遍都好。#include bits/stdc.h using namespace std; const int MAXN 35; int in[MAXN], post[MAXN]; int n; struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; Node* build(int inL, int inR, int postL, int postR) { if (inL inR) return nullptr; int rootVal post[postR]; Node* root new Node(rootVal); int pos inL; while (in[pos] ! rootVal) { pos; } int leftSize pos - inL; root-left build(inL, pos - 1, postL, postL leftSize - 1); root-right build(pos 1, inR, postL leftSize, postR - 1); return root; } void mirror(Node* root) { if (root nullptr) return; swap(root-left, root-right); mirror(root-left); mirror(root-right); } void levelOrder(Node* root) { if (root nullptr) return; queueNode* q; q.push(root); bool first true; while (!q.empty()) { Node* cur q.front(); q.pop(); if (!first) cout ; first false; cout cur-val; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } cout endl; } int main() { cin n; for (int i 0; i n; i) cin in[i]; for (int i 0; i n; i) cin post[i]; Node* root build(0, n - 1, 0, n - 1); mirror(root); levelOrder(root); return 0; }这份代码最大的特点就是“每件事都分得一清二楚”建树是建树镜像是镜像层序是层序每个函数单独拎出来都可以复用。MAXN取 35 是因为题目 N 的最大范围一般不超过 30开 35 足够你随手写个100也完全没有问题。4.2 提交结果的拆解我在本地跑样例的时候输出是4 6 1 7 5 3 2跟题目给的结果完全一致。提交到 PTA 之后常见的评测结果是“答案正确”耗时通常在几毫秒内存占用忽略不计。这道题的数据范围很小所以时间复杂度不是瓶颈。建树过程每个节点都会被中序序列里的定位循环扫一遍最坏情况是 O(n^2)但因为 N 很小完全能接受。如果你以后遇到 N 高达 10 万级别的同类题就需要用哈希表记录中序序列中每个值的位置把查找优化到 O(1)建树整体降到 O(n)。这个优化思路本身不难开一个unordered_mapint, int posMap建树前把in[i]和下标 i 塞进去定位根节点时直接查表。我建议你在刷题时也养成“先判断数据范围再决定是否优化”的习惯。像 L2-011 这种小数据题暴力查找没什么不好但如果你直接把 O(n^2) 的代码拿去跑大数据题就会白白丢分。4.3 如何用最小用例做自测程序写完后不要急着直接提交先自己造几个小用例验证逻辑。最基础的是只有一个节点1 1 1预期输出就是1。如果你的程序输出空或者报错问题一定出在边界条件上。然后再测一个只有左链的树比如3 1 2 3 1 2 3这个序列对应的是一棵只有右孩子的链1 是根2 是 1 的右孩子3 是 2 的右孩子我们来验证一下后序1 2 3根是 3中序1 2 3里根 3 在最右侧所以 3 的左子树是1 2右子树为空。递归左子树后序1 2根是 2中序1 2里 2 在右侧所以 2 的左子树是 1。整棵树就是 3 的左孩子 22 的左孩子 1一二三层分别是 3、2、1。镜像之后变成 3 的右孩子 22 的右孩子 1层序还是3 2 1。如果某种写法输出结果不对称很可能就是镜像之后左右顺序处理反了。手画两个小用例再跑代码基本能覆盖 90% 以上的低级错误。剩下的细节错误只能靠多看输出结果慢慢排查。5. 常见问题与排查技巧实录5.1 递归越界问题这个错误可以说是“重建二叉树”类题目的头号杀手。表现是程序运行时报segmentation fault或者runtime error但你对着逻辑看半天又觉得没问题。出现这种问题最常见的原因是后序区间切分时下标算错导致postL大于postR然后递归函数拿着非法区间继续访问。解决方案有两个层面。第一层代码实现层面在build函数开头加上if (inL inR) return nullptr;这个判断能拦截掉一部分越界但仍然无法完全避免非法下标访问因为后序区间可能已经越界而你还在用post[postR]。第二层也是更根本的回看左子树区间划分公式左子树后序[postL, postL leftSize - 1]右子树后序[postL leftSize, postR - 1]这两个公式我建议你推导验证一遍而不是死记硬背。理解了“后序最后一个元素是根、左子树节点数是 leftSize”之后这些下标就再也难不倒你了。5.2 左右子树区间错一位另一个高发问题是区间划分“一指禅”明明知道大致方向但左右端点总是差 1。我见过不少学员把右子树的左端点写成postL leftSize 1把左子树的右端点写成postL leftSize结果建出来的树结构完全变形。做一个简单的代入检查假设当前树只有左孩子没有右孩子那么leftSize应该等于postR - postL右子树区间长度为 0。此时右子树区间应该是[postL leftSize, postR - 1]也就是[postR, postR - 1]说明区间为空递归返回空指针完全正确。如果你把右子树左端点写成postL leftSize 1那就变成[postR 1, postR - 1]虽然递归不会访问但语义上已经有点别扭更可怕的是当右子树非空时会越界。这里给你一个自测技巧每次写好递归函数先套几个不同的用例手动跑一遍确认所有区间的左右端点都满足L R。如果某个区间出现L R说明你的切分公式有问题。5.3 多写了一个 swap有同学为了“保险起见”在建树完后又调用两次mirror想着“多交换一次应该没关系”。实际上镜像操作是幂等操作执行两次等于不执行输出结果比预期少了镜像效果答案错误没商量。为什么幂等因为每执行一次mirror所有节点的左右孩子都交换一次执行第二次时又被交换回来。这跟乘两次 -1 的道理一模一样。所以你要么只调用一次mirror要么干脆不调用、直接在层序输出时先右后左。千万不要画蛇添足。还有一个相关的坑是有同学在mirror函数里写了“先递归左子树、交换、再递归右子树”这种先交换后递归和先递归后交换有什么区别单独跑一次结果一样因为每个节点最终都会被交换一次。但如果你在交换之前就把左右子树递归处理了之后再交换实际上你交换的是已经处理完的左右子树没问题如果交换之后再递归交换后左右子树互换了递归处理的对象也变了结果依然对。两种写法都正确但新手常搞混所以我建议统一用“先交换再递归”的写法逻辑更直观。5.4 常见问题速查表症状可能原因解决方案运行报段错误递归区间越界或空指针访问检查中序定位和后序区间切分确保递归返回 nullptr 的条件正确输出结果多一行判断空树后额外输出换行只有真正有节点时才输出或在输出函数开头处理空指针输出结果全反了层序遍历时先入队了反方向子树确认镜像后层序是从左到右对应入队顺序为左孩子再右孩子输出缺数字递归边界少返回 nullptr建树函数必须覆盖inL inR的空区间情况题目样例过了但提交不过数组开小或局部变量未初始化固定数组开到题目范围以上尽量用vector动态分配这份速查表里的每一条都是我用真实报错换来的经验尤其是“输出结果全反了”这条初学者遇到得最多因为没有语法错误、没有运行时错误就是逻辑和你心里预期不一致只能靠经验定位。6. 从这道题延伸出去深度、搜索二叉树与更多变式6.1 二叉树的深度在题目里怎么用“二叉树的深度”是二叉树的经典考点经常跟这道题一起出现在各种比赛的热搜词里。那道经典的题目是给定一棵树求从根节点到最远叶子节点的最长路径上的节点数。解法可以是递归计算左子树深度和右子树深度取较大者加 1。L2-011 虽然没让你求深度但如果你能顺手在build函数里返回子树深度就能一道题同时练到建树和深度计算。求深度和建树有一个共通点都是对树做递归遍历只是返回值不同。你可以在建树之后写一个递归函数int getDepth(Node* root)遇到空节点返回 0否则返回max(getDepth(root-left), getDepth(root-right)) 1。这是二叉树所有递归问题的“母题”后面大量的路径和、直径、最近公共祖先问题都会用到这种返回值式递归。所以我的建议是刷完 L2-011 后立刻做一道求深度、再做一道求节点数的题把三种递归模式无返回值遍历、返回深度、返回节点数放到一起对比理解二叉树的基本功才算夯实。6.2 搜索二叉树和这道题的关系热搜词里还有一个“搜索二叉树”也被称为二叉排序树。搜索二叉树有一个关键性质中序遍历结果是递增有序的。为什么呢因为对于任意一个节点它的左子树所有节点值都小于它右子树所有节点值都大于它而中序遍历的顺序恰恰是先左后根再右所以整个序列自然排好了序。如果你把题目里给的“中序序列”想象成一个有序序列那么配合后序你就可以还原出一棵搜索二叉树。这在实际工程和面试里很常见给你一棵搜索二叉树的遍历序列让你重构树本质上就是上面递归建树的过程只不过可以利用有序性质更快地定位根节点位置。一个常见变式是给定一棵搜索二叉树的先序遍历让你还原这棵树。你可以利用搜索二叉树的性质把先序序列第一个元素作为根然后在剩下的序列里找到第一个大于根的元素位置左边是左子树右边是右子树。这种变式考的不是单纯的建树模板而是你对搜索二叉树性质的深层理解。6.3 变式题汇总刷题讲究“一道题带一片”。围绕 L2-011 我帮你把相关变式题画个谱系中序先序重建二叉树思路完全对称先序第一个元素是根然后去中序里定位。中序后序重建镜像树就是本题只是可以换用不同策略。层序中序重建二叉树层序的第一个元素是根剩下的元素根据中序划分到左右子树集合递归继续。求任意两节点的最近公共祖先建好树后用递归查找两个节点在左右子树中的分布情况。判断两棵二叉树是否互为镜像递归比较一树的左孩子和另一树的右孩子。输出二叉树的右视图层序遍历取每层最后一个节点。这堆题看起来五花八门但核心能力都是一样的对树的遍历有透彻理解。我个人认为 L2-011 之所以叫“玩转二叉树”就是因为它要求你在建的树、遍历序列、镜像变换之间反复横跳玩明白了以上这些题自然就通了。有个很实用的学法是把你手头题库里所有跟二叉树遍历相关的题集中起来在两周内连续刷完每天至少手写一遍建树递归。这种刻意练习比一次性刷十道同类题效果更好因为间隔能让你反复记住递归边界和区间划分。等你做到闭着眼睛都能写出build函数的时候L2 的二叉树题对你来说就只是一层窗户纸了。最后说句实在话建树递归第一次写不出来太正常了我当年也是对着网上的代码一行一行抄抄熟了才明白那些下标为什么这样切。关键是你别停在“抄”这一步合上屏幕自己推演一遍、画一遍、写一遍这个过程比看十篇解析都管用。等你亲手把1 2 3 4 5 6 7和2 3 1 5 7 6 4玩明白这道题你就算真正吃透了。