PTA上这道“树与二叉树 2 根据先序中序遍历序列构造二叉树”我当年第一次做的时候整整卡了一个下午。不是看不懂题目而是对着样例左右推演都觉得自己懂了一写代码就Recursion到底、数组越界、Segment Fault。身边同学也几乎都在这里栽过跟头后来去查PTA讨论区发现“为什么写二叉树程序总是报运行时错误”简直就是每周必有人问的热词。这道题本身其实不难难就难在你是不是真搞懂了“先序和中序遍历是怎么共同决定一棵树的形态”。如果只是背模板碰到变体题照样不会。这篇我不打算给你“完美的标准答案”而是把这个题背后那套“递归划分区间”的逻辑彻底拆开配上可跑的代码、常见的坑、以及从这道题延伸出去的考点。你只要能静下心把这篇从头看到尾把递归调用关系在纸上画一遍以后碰到中序后序、层序输出、求树高、判断完全二叉树这些PTA高频题都会顺很多。1. 先序中序为什么能唯一还原一棵二叉树1.1 两种遍历各自扮演什么角色先序遍历的顺序是根节点、左子树、右子树。这意味着你拿到先序序列第一眼就能确定谁是这个树的根。中序遍历的顺序是左子树、根节点、右子树。这意味着在中序序列里根的左边一定是它的左子树全体节点右边一定是右子树全体节点。这两条信息叠加在一起就构成了一个天然的递归结构先序第一个节点是根去中序中找到这个根中序序列就被切成左右两段左边是左子树的中序右边是右子树的中序。接下来回到先序序列按照左右子树各自的节点数量把先序剩余部分也切成两段左边就是左子树的先序右边就是右子树的先序。于是你又得到了两个规模更小的“先序中序”子问题继续递归解下去。这个过程可以类比成玩拼图先序告诉你整张图的轮廓边界在哪中序告诉你在边界内部哪些元素该放在左侧、哪些放在右侧。每次递归你都在“缩小地图范围”直到地图上只剩下一个点。1.2 为什么先序后序就不能唯一确定而先序中序可以很多人学到这里会产生一个疑问先序后序行不行答案是不行。先序和后序都只反映“根”的位置关系先序的根在最前面后序的根在最后面但两者缺失了“左子树和右子树之间的分界信息”。举个例子一棵树只有一个左孩子和一棵树只有一个右孩子先序和后序序列完全一样但树的形状完全不同。中序恰好提供了这个分界所以先序中序或中序后序能唯一还原二叉树而先序后序单独配对不行。这也直接解释了为什么PTA这道题特意强调“先序中序遍历序列”而不是随便给你两种遍历顺序。题目设计本身就在考察你对遍历本质的理解而不只是让你机械地模拟递归建树。1.3 手把手推演一行一行拆解递归区间先拿一个教科书级的例子。假设题目给的是先序: A B D E C F 中序: D B E A C F第一步看先序的第一个字符A它是这棵树的根。第二步去中序里找A的位置下标是3从0开始数于是中序被分成两段左子树中序下标0~2内容 D B E右子树中序下标4~5内容 C F第三步左子树的中序有3个节点意味着先序里A后面紧跟着的3个节点是左子树的先序左子树先序B D E右子树先序C F第四步递归处理“先序BDE 中序DBE”这个子问题先序第一个是BB就是左子树的根中序里找B在下标1的位置左边是D右边是E于是B的左孩子是D右孩子是E第五步再递归处理“先序CF 中序CF”这个子问题先序第一个是CC就是右子树的根中序里C在位置0左边为空右边为F于是C的右孩子是F最终树的结构是A / \ B C / \ \ D E F这一步一步的“找根——切中序——数个数——切先序——递归”就是整个题的核心字节。你能把这个流程在纸上熟练推演代码就只是翻译工作。2. 递归函数的设计四个下标参数怎么传才不懵2.1 为什么不用字符串切片而要用下标范围很多初学者第一反应是每层递归都把字符串切出一个子串传下去比如C语言里复制一段char数组或者C里传substr。这在数据量小的时候看着挺直观但实际上既浪费内存又容易出错更重要的是它不符合二叉树的递归本质你切来切去最后还是要回到同一个原始序列里定位节点。PTA这类OJ环境里更标准也更高效的做法是始终保留原始的pre数组和in数组递归函数里只传四个整数下标限定当前子问题在原始数组里的可见范围。四个参数分别是preL当前子树在先序序列中的左边界下标preR当前子树在先序序列中的右边界下标inL当前子树在中序序列中的左边界下标inR当前子树在中序序列中的右边界下标只要这四个下标围出的区间不交叉就说明当前子树至少还有一个节点一旦preL大于preR说明这个子树是空的函数返回NULL。2.2 核心逻辑先从先序拿根再拿根去中序“切区间”递归体总共就做三件事第一件事创建根节点。当前先序区间的左端点preL对应的一定是当前子树的根直接取这个位置的字符作为根节点的val。第二件事在中序区间[inL, inR]里找到根节点的位置k。这个查找过程用for循环逐个比较就行因为题目保证序列里的字符不重复。第三件事计算左子树节点个数。左子树的节点数量就是k - inL因为中序序列里从inL到k-1全都是左子树节点。有了这个数量就可以把先序区间也划分为左子树的先序范围[preL1, preLleftCount]右子树的先序范围[preLleftCount1, preR]对应的中序范围自然是左子树中序范围[inL, k-1]右子树中序范围[k1, inR]然后对这两个子区间分别递归调用buildTree函数把返回值挂到当前根节点的left和right指针上。2.3 三个边界细节决定递归能否正确终止这个题的递归终止条件是“区间为空”而不是“当前节点没有孩子”。判断区间为空的标志就是preL preR。很多人写成preL preR就回溯这会导致单节点子树再次尝试递归构造它的左右子树而左右子树区间是空的但函数继续往下走最终访问到无效下标程序直接崩。第二个容易犯错的地方是查找根节点位置时查找范围必须是当前子问题的中序区间[inL, inR]而不是整条中序序列。虽然理论上同一个字符在中序里只出现一次但如果你的代码每次都在[0, length-1]里找一旦把左右子树的区间算错就会找到错误位置后续划分也会全面崩盘。第三个细节是leftCount这个变量必须单独计算不可偷懒直接用k - inL 1去推右子树的下标。右子树先序的起始位置是preL leftCount 1不是preL (k - inL 1)虽然这两者数值恰好一样但逻辑含义完全不同混在一起写到后面你自己都说不清每个下标的含义。3. 完整代码实现从节点定义到PTA提交全过关3.1 先写清楚二叉树的节点结构在C语言环境下节点结构体一般这么写typedef struct TNode { char val; struct TNode *left; struct TNode *right; } BTNode;如果是C环境建议直接在结构体里写构造函数struct BTNode { char val; BTNode *left; BTNode *right; BTNode(char v) : val(v), left(NULL), right(NULL) {} };构造函数的好处是每次新建节点时不用手写两行赋值代码也不容易漏初始化指针。OJ环境里漏初始化指针是运行时错误的重灾区指针不置空后面遍历时就会访问到野地址。3.2 递归建树函数把推演过程翻译成代码C语言版本BTNode* buildTree(char *pre, char *in, int preL, int preR, int inL, int inR) { if (preL preR) { return NULL; } BTNode *root (BTNode*)malloc(sizeof(BTNode)); root-val pre[preL]; root-left NULL; root-right NULL; // 在中序区间 [inL, inR] 中找到根节点所在位置 int k inL; while (in[k] ! pre[preL]) { k; } int leftCount k - inL; // 左子树节点个数 root-left buildTree(pre, in, preL 1, preL leftCount, inL, k - 1); root-right buildTree(pre, in, preL leftCount 1, preR, k 1, inR); return root; }C版本几乎一样只是把malloc换成newBTNode* buildTree(string pre, string in, int preL, int preR, int inL, int inR) { if (preL preR) return NULL; BTNode *root new BTNode(pre[preL]); int k inL; while (in[k] ! pre[preL]) k; int leftCount k - inL; root-left buildTree(pre, in, preL 1, preL leftCount, inL, k - 1); root-right buildTree(pre, in, preL leftCount 1, preR, k 1, inR); return root; }3.3 主函数怎么调用别把边界参数传错主函数调用时要传入完整区间的端点坐标。比如先序和中序字符串长度都是n那么首次调用应该是BTNode *root buildTree(pre, in, 0, n - 1, 0, n - 1);这里最容易犯的错是把preR和inR传成n而不是n-1。二叉树的序列数组下标从0开始右边界必须是最后一个有效元素的下标。传成n函数进入递归后会多出一次无效区间的判断虽然多数情况下preL preR的判断能拦住但如果你把preR当成区间长度来用后续leftCount计算就会整体偏移一位最终构造出来的树形状完全不对。还有一个细节是输入的读取。PTA这道题经常是两行字符串第一行先序、第二行中序。C语言里直接scanf(%s, pre)就能一次读取不含空格的字符串不需要逐字符处理。如果题目样例里有空行或者回车记得在scanf前面加一个getchar()吃掉换行避免字符串读到空串。这个问题看着小但PTA的判题数据里真有这种坑不少同学的“答案错误”就是这么来的。3.4 完整可提交参考代码下面给一份可以直接拿去做模板的C完整代码加了后序遍历输出方便你在本地验证构造结果是否正确#include iostream #include string using namespace std; struct BTNode { char val; BTNode *left; BTNode *right; BTNode(char v) : val(v), left(NULL), right(NULL) {} }; BTNode* buildTree(string pre, string in, int preL, int preR, int inL, int inR) { if (preL preR) return NULL; BTNode *root new BTNode(pre[preL]); int k inL; while (in[k] ! pre[preL]) k; int leftCount k - inL; root-left buildTree(pre, in, preL 1, preL leftCount, inL, k - 1); root-right buildTree(pre, in, preL leftCount 1, preR, k 1, inR); return root; } void postOrder(BTNode *root) { if (root NULL) return; postOrder(root-left); postOrder(root-right); cout root-val; } int main() { string pre, in; cin pre in; int n pre.size(); BTNode *root buildTree(pre, in, 0, n - 1, 0, n - 1); postOrder(root); cout endl; return 0; }把第一节那个例子喂进去输入ABDECF DBEAFC输出后序应该是DEBFCA你手动跑一遍后序遍历验证一下D、E、B、F、C、A正好对应“左、右、根”的顺序说明树构造正确。4. 一跑就崩的“运行时错误”三个典型现场还原4.1 递归没有正确的终止条件导致无限下钻访问野内存这是PTA论坛里“写二叉树程序时为什么总是报运行时错误”最常见的根源。很多人的递归开头写的是if (preL preR) { return root; }乍一看单个节点时直接返回没毛病。但问题出在这个节点还有左右子树时递归继续调用buildTree构造左子树和右子树而这两个子问题的区间都是空的传入的参数如preL2、preR1此时preL preR函数体却没有这个分支来返回NULL于是继续往下执行。malloc一个节点然后试图在空区间里查找根节点k会在中序数组里一路搜下去直到越界最后不是读到垃圾值就是触发访问违例。正确的做法是判断preL preR而不是preL preR。一个包含当前根节点的区间当它只有一个节点时还要继续构造它的左右子树只不过左右子树区间为空自然就返回NULL。递归的收敛靠的正是这个空区间判断。4.2 查找根节点时没限制在中序区间内找到错误位置另一种隐蔽的错误是查找根节点的循环条件写成while (in[k] ! pre[preL]) k;但k的初始值是0而不是inL。在当前子树的中序范围内根节点一定存在所以一定能找到。问题在于如果当前子树的根在中序区间之外也出现了相同字符虽然题目说不重复但如果你对区间下标理解有偏差k其实已经滑出了[inL, inR]查找就会跑到别的子树区域去。更常见的情况是你在递归过程中把inR传错了比真实右边界大导致k越过当前子树的中序区间进入其他子树的区域找到的“根”其实是另一个节点的位置。排查这类问题时建议在循环里加入区间约束int k inL; while (k inR in[k] ! pre[preL]) k; if (k inR) { // 打印 preL, preR, inL, inR 和当前根字符方便定位 }把异常情况显式暴露出来比让程序稀里糊涂崩溃好得多。4.3 递归调用的下标计算错误导致左右子树互换还有一类错误不崩溃但构造出的树长歪了。比如左子树先序范围的右边界写成了preL leftCount而不是preL leftCount 1之类的细微差异。这类问题最坑的是输入数据规模小的时候可能碰巧能通过一旦样例变长就露馅。调试这种逻辑错误我个人的经验是每层递归都打印当前要处理的四个区间和根节点字符。比如printf(build(%d,%d,%d,%d) root%c\n, preL, preR, inL, inR, pre[preL]);然后和手动推演的区间对比第一层、第二层、第三层……哪一层对不上错误就出在哪一层的参数传递上。这一步比任何调试器都直观尤其适合OJ环境里不能打断点的场景。5. 常见问题速查表提交前逐条自查我把这题最容易犯的五个错误整理成一张表提交代码之前对照自查一遍AC率能明显提高。错误类型错误表现排查方向递归终止条件写成preLpreR单节点子树继续递归数组越界崩溃改成preL preR返回NULL查找根节点时k的初始值不是inL子树区间内查找范围失控确保查找区间是[inL, inR]左子树节点个数计算错误构造出的树形状错乱检查leftCount k - inL是否写对首次调用时preR/inR传成n区间多出无效元素右边界传长度减一malloc或new的节点没初始化指针遍历时访问野指针左右孩子必须置空自查的时候不只要看代码还要在脑子里跑一个小样例。我每次提交前都会用一个长度为3的树做测试比如先序ABC、中序BAC手推结果是根A、左孩子B、右孩子C。如果这个最小样例的递归参数都传对了复杂样例大概率也不会出问题。6. 从这道题延伸出去PTA二叉树系列的高频考点6.1 中序后序构造二叉树逻辑完全对称很多同学在建树这题过了之后转头遇到“中序后序”的PTA题又懵了。其实逻辑完全对称。后序遍历的特点是根在最后所以去后序序列里取最后一个字符当根然后在中序里划分左右子树区间接着计算左子树节点个数再去后序序列里做区间划分。唯一的差别在于后序序列中左子树的先序范围从postL开始延续leftCount个右子树从postLleftCount到postR-1因为最后一位是根。如果你能画出这段区间的划分图这类题就是送分题。6.2 构造完树之后层序输出、求树高、判断完全二叉树PTA的天梯赛L2组题目里很多都以“先序中序构造二叉树”为前置步骤然后再让你做点别的事。最常见的是层序输出用队列BFS遍历一层一层打印节点值。这里有个输出格式的坑PTA要求行末不能有多余空格所以通常的做法是记录当前是否为首个输出节点是就不打空格否则先打一个空格再打节点值。比如L2-006树的遍历就是这么一道经典题先给你后序和中序让你构造树然后层序输出。你如果只会建树不会层序照样拿不到分。层序BFS的模板代码void levelOrder(BTNode *root) { if (root NULL) return; queueBTNode* q; q.push(root); bool first true; while (!q.empty()) { BTNode *cur q.front(); q.pop(); if (!first) cout ; cout cur-val; first false; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }6.3 线索二叉树和普通二叉树遍历的关系很多同学看到“线索二叉树”这个热词会觉得是另一座大山但其实线索二叉树解决的问题就是普通二叉树的递归遍历需要系统栈或者手动栈而不能直接沿着指针顺序访问下一个节点。线索二叉树通过把空指针改造成前驱和后继线索让遍历可以不用栈。理解了先序中序构造二叉树之后你会更深刻体会到“中序序列”本身就是一种线性顺序。线索化就是在中序序列的基础上给每个节点加上“前驱”和“后继”的指针。这也是为什么很多教材把线索二叉树放在遍历之后讲——因为它的核心就是利用中序序列来定义逻辑顺序。PTA的某些进阶题会要求你输出线索化后的节点顺序这本质上还是在考你对中序遍历的掌握。6.4 为什么题目输入序列中的字符不会重复这是考点也是助攻PTA这道题的题目描述里通常会保证序列中的元素互不相同。这个保证不是随便写的它是整个算法成立的前提。如果元素有重复你先序里取到根字符去中序里找位置时会有多个候选位置树的形态就不唯一。如果你后面做设计题自己造数据时必须保证序列元素不重复否则算法失效。反过来想这个保证也是你的助攻查找根节点时不用处理重名冲突直接用最朴素的for循环即可。面试中如果被问到“元素重复怎么处理”标准做法是把序列元素改成带下标的二元组或者用位置信息区分相同字符但PTA考查的基本功还是“不重复”这个前提下的解法。7. 我在实际调试这题时的几个习惯最后说点代码之外的体会。我调试这种递归建树的题第一件事永远不是看代码而是拿样例在纸上画递归树。每一层递归对应一个区间范围画出来之后你才会发现递归函数不是在“生成”一棵二叉树而是在“还原”一棵本来就存在的树。你做的每一步都是对已有信息的解析而不是创造。第二件事是我会故意写错一两个参数观察程序怎么报错然后反向验证自己对区间的理解。比如故意把leftCount传成leftCount 1程序多半会栈溢出或者构造出错误树这时候看你打印的每层区间就能强化记忆左子树的先序右边界是preLleftCount绝不是别的。第三件事是别急着优化。很多同学看到递归就想着改成非递归、用栈模拟、或者搞什么迭代版。PTA这道题的数据量很小递归完全够用栈溢出不可能发生。你真正要优化的是自己的“区间推导肌肉记忆”。等你能闭着眼把四种遍历的区间划分写对再去碰非递归也不迟。第四个习惯也是被坑出来的教训每次提交前检查一下输入函数有没有正确处理换行符。C语言的scanf和C的cin在换行处理上有差异C的cin string会自动跳过空白字符所以最稳妥的方式是用C的cin读取字符串。如果你用C语言的scanf要在读字符串之前处理掉可能的换行否则会把空串读进去然后buildTree里的while循环查不到根字符k一路越界直接运行时错误。先序中序构造二叉树说白了就是“找根—切中序—算数量—切先序—递归”这五步的循环。这五个字看着平淡但能把每一步的下标推导做到肌肉记忆的人写任何二叉树题都会很稳。P