先序加中序遍历重建二叉树这题在PTA上属于“树与二叉树”板块的经典题也是后续学习线索二叉树、二叉搜索树、平衡树之前必须迈过去的一道坎。很多同学卡在这道题上倒不是递归思路不理解而是写出来的程序要么段错误、要么答案错误改来改去都不知道哪一步出了问题。我曾经带过不少刷题群每次一到这题群里提问量总是突然暴增而且翻来覆去就那么几个坑。这篇就用自己的实操经验把从原理到代码再到排错的全过程掰开揉碎讲一遍适合刚开始刷二叉树题目、或者已经刷过几题但想彻底搞懂这题的读者。1. 为什么“先序中序”能唯一确定一棵二叉树1.1 两个遍历序列各自能提供什么信息先序遍历的顺序是“根-左-右”所以先序序列的第一个节点一定是整棵树的根节点。这个结论在任何情况下都成立因为先序遍历从根出发第一个访问到的必然是它。单凭这一点我们就能从先序序列里直接拿到根。中序遍历的顺序是“左-根-右”它最核心的价值在于一旦知道了根节点是谁就能在中序序列中把根的位置找出来根左边那一整段就是左子树的中序序列根右边那一整段就是右子树的中序序列并且左右两段的长度也就确定了。这里有个关键点一棵二叉树中无论先序、中序还是后序左子树的节点数在三个序列里都是一样的。也就是说先序序列中根节点之后紧跟着的那 lenLeft 个节点就是左子树的先序序列剩下的就是右子树的先序序列。一棵树的子树节点集合相同遍历顺序不同罢了。1.2 两者组合的“完整信息链”先序提供根中序提供左右划分两者一组合就形成了完整的递归信息链每一层递归都先用先序找到根再用中序切分左右然后带着更小的左右子序列分别进入下一层递归。用生活里的例子类比先序序列相当于一张名单每次都告诉你“这组人的领头是谁”中序序列相当于按位置排好的队伍你知道领头的站在队伍的哪个位置左边就是左队、右边就是右队。两队内部再用同样的规则继续拆分。整个过程就像不停地切豆腐每次切一刀两边各成一块每块再切直到切到只剩一块。1.3 为什么不能只用先序或只用中序只用先序只能确定根不知道谁左谁右一个先序序列可以对应成千上万种不同的树形。只用中序连根都找不出来因为没有“第一个是根”这种信息。所以这两个序列必须配合使用先序提供根中序提供位置二者缺一不可。这一点在面试里也常被追问理解了这一层题目才算真正吃透。2. 核心实现递归构造二叉树的思路与代码拆解2.1 递归函数的参数设计以PTA常见的函数题形式为例BiTree CreateBiTree(char *pre, char *in, int len)参数含义分别是pre当前子树的先序序列首地址in当前子树的中序序列首地址len当前子树的节点个数设计成“首地址长度”的形式比传一堆下标要灵活尤其适合在递归调用里用指针加减来缩小子树范围。也有不少教材和题库改成传数组下标的形式比如BiTree CreateBiTree(char pre[], int preL, int preR, char in[], int inL, int inR)两种都行核心逻辑完全一样。PTA上两种写法都能过只要边界处理对。我个人习惯前缀和后缀都用下标因为查错的时候能直接把数组段打印出来直观很多。2.2 递归体内部的三步操作第一步从先序拿到根节点创建根节点BiTree T (BiTree)malloc(sizeof(struct TNode)); T-Data pre[0];第二步在中序序列中找到根的位置。最简单的做法是线性扫描因为节点总数一般不大扫描的开销可以忽略int i; for (i 0; i len; i) { if (in[i] pre[0]) break; }找到之后根左边有 i 个节点根右边有 len - i - 1 个节点。第三步递归构造左右子树T-Left CreateBiTree(pre 1, in, i); T-Right CreateBiTree(pre i 1, in i 1, len - i - 1);注意左右子树的先序和中序起点为什么这么偏移左子树先序先序序列第1个是根所以从pre1开始长度正好是 i左子树中序从in开始长度是 i右子树先序根节点占了1个节点左子树占了i个节点所以右子树从pre1i开始右子树中序根的位置在ini右子树从ini1开始递归的终止条件就是len 0此时返回 NULL。很多同学容易漏掉len 0的情况导致递归一路越界访问下去直到系统崩溃。2.3 完整代码示例#include stdio.h #include stdlib.h #include string.h typedef struct TNode { char Data; struct TNode *Left; struct TNode *Right; } *BiTree; BiTree CreateBiTree(char *pre, char *in, int len) { if (len 0) return NULL; BiTree T (BiTree)malloc(sizeof(struct TNode)); T-Data pre[0]; int i; for (i 0; i len; i) { if (in[i] pre[0]) { break; } } T-Left CreateBiTree(pre 1, in, i); T-Right CreateBiTree(pre i 1, in i 1, len - i - 1); return T; }2.4 手动推演一轮递归过程用一棵简单二叉树举例A / \ B C先序序列A B C 中序序列B A C第一层递归pre[0] A根为 A在中序 B A C 中找到 A 的下标 i 1左子树中序B长度 1右子树中序C长度 1进入左子树递归CreateBiTree(pre1, in, 1)pre 为 B Cin 为 B进入右子树递归CreateBiTree(pre2, in2, 1)pre 为 Cin 为 C左子树递归里pre[0] B中序只有 B找到 i0左右子树 len 都为 0递归返回 NULLB 节点诞生。右子树同理C 节点诞生。整棵树还原成功。这个推演过程建议手写几遍尤其是画箭头标出每次指针偏移的位置。递归这东西眼睛看会了不算会手推三遍才能真正建立起肌肉记忆。3. PTA运行时错误的典型原因与排查方案热词里“写二叉树程序时为什么总是报运行时错误”长期居高不下说明这是个普遍痛点。PTA的运行时错误通常对应段错误Segmentation Fault本质就是内存访问越界。结合这道题最常见的有四种。3.1 递归出口写错最常见的写法错误是只判断len 0而不是len 0导致 len 传入负数时继续往下跑。什么时候 len 会变成负数中序序列里找不到根节点也就是 i 一直循环到 len 都没匹配最后 i len。此时 len - i - 1 -1传入右子树递归len 为负数循环都不会进直接就是灾难。更致命的是这种情况下pre[0]还在读取数组越界几乎必然发生。3.2 中序查找时未处理找不到的情况正常情况下题目保证先序和中序来自同一棵树一定能找到。但如果你自己造测试数据或者从文件读入时格式有问题就可能出现找不到根的情况。所以稳健的写法是循环结束后判断 i 是否等于 len如果是就说明输入数据非法此时应该报错而不是继续递归if (i len) { // 数据非法这里可以打印提示或直接返回 NULL return NULL; }PTA的题目一般数据都合法但加了这一步排查自己的bug时会容易很多。3.3 指针偏移算错左右子树递归调用时的偏移量是重灾区。我见过不少同学写成T-Right CreateBiTree(pre i 1, in i, len - i - 1);中序的偏移少了1。为什么错中序中根的位置在in[i]右子树应该从根的下一个位置开始即in i 1。如果写成in i右子树的中序序列里就多了一个根节点递归进去之后在序列里找根永远能找到自己但划分必然出错最终导致越界访问。还有更隐蔽的先序偏移写成pre len - i这种看起来差不多实际差之毫厘谬以千里。建议写完之后用一个三层、五层的对称二叉树手动走一遍把每次递归传入的地址段打印出来对照。3.4 内存分配失败未检查PTA的测试点一般不会极端到让 malloc 失败但写工程级代码时还是应该检查BiTree T (BiTree)malloc(sizeof(struct TNode)); if (T NULL) { // 处理分配失败 }加分项但平时刷题图省事可忽略。真正要命的是另一件事malloc 出来的节点没有初始化 Left 和 Right 指针。如果不显式赋值这两个指针就是野指针。后续遍历时一旦访问到未赋值的左右子树段错误就来了。所以在递归函数里创建节点后立刻把 Left 和 Right 置为 NULL 是保命习惯T-Left NULL; T-Right NULL;4. 从“通过测试”到“真正理解”如何自查与扩展4.1 用不同形态的树验证代码正确性PTA给的测试点数量有限自己必须补几组特殊形态的数据重点测三种完全二叉树节点数较多左右子树均匀分布验证常规递归是否正确只有右子树的单支树先序 A B C中序 A B C根永远在中序的第0位验证 i0 时左子树 len0 的处理只有左子树的单支树先序 A B C中序 C B A根永远在中序的最后一位验证右子树 len0 的处理这三组跑通了基本可以确定边界处理没问题。另外随机生成若干颗树把先序和中序序列打印出来再重建并打印后序与原树的后序对比是“暴力验证”的好办法。4.2 输出验证如何检查重建出来的树很多同学只验证“重建过程没报错”但没验证“重建结果对不对”。一个简单粗暴的方法是写一个后序遍历把输出结果和原树的后序序列比较。如果二者一致那重建基本就是对的。原理是先序中序唯一确定一棵二叉树所以重建出来的树必须和原树结构完全一致遍历结果也必须一致。也可以写一个层序遍历来验证把每层节点按顺序打印出来肉眼观察结构。但层序比后序麻烦需要队列辅助新手阶段用后序验证就够了。4.3 相关变体题一网打尽PTA和天梯赛里这个知识点的变体很多但核心逻辑都是同一套已知后序中序求二叉树后序最后一个节点是根其余步骤和先序中序几乎一样已知先序中序求后序不建树直接在递归过程中输出根节点放在递归完左右子树之后已知后序中序求先序同理先输出根再递归左右判断一棵树是否为完全二叉树常结合层序遍历用空指针标记法个人建议把这题AC之后立刻自己动手补写“用已知先序中序输出后序”的实现不建树版和建树版各写一遍。这一步做完对这个知识点的理解就彻底通透后续遇到任何变形题都不会慌。5. 实操心得我给初学者的几条建议第一先手算再码代码。拿到题目先手写一个三层的树写出它的先序和中序然后手动模拟递归全过程把每层递归的 pre、in、len 都列出来。这一步看起来很笨但对训练递归思维特别有效比直接写代码再改错误快得多。第二针对“中序查找根位置”这一步可以用循环变量命名成容易看懂的名字比如leftLen、rightLen而不是i、j。PTA的判题只关心代码功能不在乎变量名但你自己回头看的时候会发现语义清晰的变量名能让查错效率提升一大截。第三建议保存一份自己的“二叉树模板代码”包括节点定义、建树函数、先序中序后序层序遍历函数、求深度/节点数函数等。每次碰到树相关题目直接从这个模板开始改而不是从零敲省时间也降低出错率。第四PTA报运行时错误时不要只盯着提交页面看本地用编译器跑一下配合打印中间变量定位错误层。我自己的习惯是在递归函数入口打印当前 pre、in 的首字符和 len这样能清楚看到递归到哪一步才出的问题。最后再分享一个治本的调试技巧数据规模小的时候用断点单步走一遍建树函数然后把每次T-Left和T-Right的值记录下来对照手工推演的结果。调试器用熟之后你会发现二叉树相关题目的错误基本都是“考虑不周”和“边界不熟”两种见多了自然就形成条件反射了。