先序+中序序列构造二叉树：原理、递归实现与PTA实战复盘

先声明一下这篇写的是我本人在刷PTA数据结构题时对根据先序中序遍历序列构造二叉树这道经典题目的完整复盘。不是单纯贴一份能过的代码而是把我从看得懂思路到能自己推导、自己调试、不惧变形题的全过程拆给你看。如果你正在准备PTA的树与二叉树专题、应付期末考试或者刷天梯赛的L2题目这篇文章应该能帮你省下不少弯路。让我先把这个题目的实际分量说清楚题目本身只要求你写一个建树函数输入是先序序列和中序序列输出是层序遍历或者后序遍历序列不同版本要求不同但核心都是先构造出这棵二叉树。但就是这道基础题每年都能挂掉一大批人。我见过很多同学递归逻辑背得熟一上机全懵归根结底是没搞明白两个序列到底是怎么咬合在一起的。所以这篇文章我不打算只给代码而是把底层逻辑、推导过程、易错点以及变体题的应对方式全部梳理一遍让你是真的会了不是背了。1. 先序中序凭什么能唯一确定一棵二叉树这是整个问题的地基。如果你还没想明白这一点就急着写递归后面一定会被下标搞晕。我们先从最根本的问题出发给一棵二叉树先序遍历和中序遍历分别能得到什么先序遍历的顺序是根、左子树、右子树。也就是每到一个节点先记录它自己再递归地遍历左子树最后再递归地遍历右子树。所以先序序列的第一个元素必然是整棵树的根节点——这一点毫无悬念也是我们解题的第一个突破口。中序遍历的顺序是左子树、根、右子树。注意这里的左子树是整个左子树包含的所有节点而不仅仅是一个左孩子。所以在中序序列里找到根节点之后根节点左边的所有元素就是整棵左子树的节点集合右边的所有元素就是整棵右子树的节点集合。看到这里两件事就自然浮出来了先序序列告诉我们谁是谁的根因为它把根放在最前面。中序序列告诉我们根的左右两边各有哪些节点也就是帮我们切分左右子树。你可能要问那为什么必须两个序列配合单独一个序列行不行单独给先序序列你只知道根是第一个但左子树有哪些节点、右子树有哪些节点完全不知道。比如先序是 A B C它可能是这样的链状树根 A 只有右孩子 BB 只有右孩子 C也可能是根 A 的左孩子是 BB 的左孩子是 C。光凭先序根本分不清。中序序列单独给也一样我们知道整棵树的最左节点是 B但它和根隔着多少节点、根到底是哪一个完全无法判断。左右子树一旦分不清边界树就千变万化自然无法唯一确定。那为什么先序中序就能确定因为这两个序列提供的信息恰好互补。用一个很朴素的递归思想来理解先序第一个节点确定根中序里以这个根为界左边一堆节点天然就是左子树的家底右边一堆节点就是右子树的家底。有了哪些节点属于左子树这个集合我们再回到先序序列里紧随其后的若干节点数量等于左子树节点数就顺理成章地成为左子树的先序序列再往后的就是右子树的先序序列。这样递归的每一层都同时拿到了当前子树的先序序列和当前子树的中序序列问题规模减半子问题与原问题完全同构。这里顺带记一个结论先序中序可以唯一确定二叉树后序中序也可以唯一确定二叉树但先序后序不能唯一确定二叉树。因为先序和后序都能给出根的位置但无法判断孩子的左右归属。面试或考试里经常遇到这个概念题理解了这个游戏规则怎么问都不怕。再往下走既然确定了思路接下来就是怎么把序列的边界切准确。这一步看起来简单但几乎所有人写代码第一次都会在这翻车。2. 分治推导手算一遍比看十遍代码更管用我强烈建议你在写代码之前先拿一组数据从头到尾在纸上推导一遍。这一步能帮你把递归过程中每个序列的哪一段属于左子树、哪一段属于右子树彻底印在脑子里。我们拿一个实际例子来说。假设先序序列是ABDGHCEIF中序序列是GDHBAEICF。第一步先序第一个是 A所以 A 是整棵树的根。在中序序列里找到 A 的位置中序序列是 G D H B A E I C FA 的下标是 4。于是 A 左边有 GDHB 这4个节点属于左子树右边有 EICF 这4个节点属于右子树。到这里我们已经知道左子树有 4 个节点右子树有 4 个节点。第二步回到先序序列 ABDGHCEIFA 已经用掉了。接下来 B 后面跟着的、数量等于左子树节点数4个的节点即 BDGH就是左子树的先序序列剩下的 CEIF 就是右子树的先序序列。于是问题一分为二左子树的先序是 BDGH中序是 GDHB。右子树的先序是 CEIF中序是 EICF。你看每一棵子树又一次拿到了它的先序和中序。我们用同样的规则处理左子树先序 BDGH 的第一个节点 B 是子树的根。在中序 GDHB 里找到 B下标是 3B 左边是 GDH 三个节点属于 B 的左子树B 右边没有节点所以右子树为空。那么左子树的左子树先序为 DGH中序为 GDH左子树的右子树为空。继续拆 DGH先序 DGH 中 D 是根中序 GDH 中 D 的下标是 2左边 G 在 D 的左子树H 在 D 的右子树。递归下去G 和 H 都是叶子节点整棵左子树就构造完毕了。右子树同理先序 CEIF 中 C 是根中序 EICF 中 C 的下标是 3左边 EI 是左子树右边 F 是右子树。再拆 EI先序 EI 中 E 是根中序 EI 中 E 的下标是 0右边 I 是右子树。到这里整棵树就全部推导出来了。这棵树的形状是A / \ B C / \ / \ D H E F / \ G I注意看这里的层序遍历是 ABCDHFGEI后序遍历是 GHDBIEFCA。题目如果要求你输出层序或者后序建树之后再做一遍遍历就完了。上面这个手算过程本质上就是一个不断确定根、切分左右、递归下去的过程。这个过程的每一步对应到代码里其实就是几个关键的边界参数。我看很多同学写递归时喜欢在脑袋里空转递归但纸上走一遍之后递归里每个参数的含义就具象了写代码的时候你甚至可以照着草稿翻译。3. 代码实现下标处理是唯一的重头戏把纸上的推导翻译成代码最主流的方式是递归函数或者用栈模拟非递归。我个人建议先把递归版本吃透因为它和推导过程是严格一一对应的写完不容易出错。3.1 递归函数签名与出口设计我们先设计递归函数。常规写法是传入五个参数先序序列、中序序列、当前子树在先序序列中的范围、当前子树在中序序列中的范围。TreeNode* build(vectorchar preorder, vectorchar inorder, int preL, int preR, int inL, int inR) { // 递归出口区间不合法说明没有节点了 if (preL preR || inL inR) { return nullptr; } // 先序序列区间的第一个节点就是当前子树的根 char rootVal preorder[preL]; TreeNode* root new TreeNode(rootVal); // 在中序序列当前区间内找到根节点的位置 int rootIdx -1; for (int i inL; i inR; i) { if (inorder[i] rootVal) { rootIdx i; break; } } // 左子树包含的节点个数 int leftSize rootIdx - inL; // 递归构建左右子树 root-left build(preorder, inorder, preL 1, preL leftSize, inL, rootIdx - 1); root-right build(preorder, inorder, preL leftSize 1, preR, rootIdx 1, inR); return root; }这个函数是整道题的核心寥寥几行但每一个边界都值得你反复推敲。先说递归出口。当 preL preR 时表示当前先序区间已经没有元素了子树为空。此时返回 nullptr。这里有个细节inL inR 其实和 preL preR 是等价的因为先序区间长度和中序区间长度一定相同所以只要第一个条件成立即可。但为了保险起见两个条件都写上并不会错。再说中序里找根。常规做法是写一个 for 循环从 inL 扫到 inR找到与根值相等的位置。只要节点值互不相同PTA 这道题通常保证这个位置是唯一的。扫描的复杂度是 O(n)加上递归每层都要扫整体 O(n^2)。如果序列长度特别大比如到了 10^5 这个量级O(n^2) 就危险了。优化方案是提前把中序序列每个值对应的下标存进哈希表这样每次找根就是 O(1)。下面我会单独说这个优化先在基本版基础上把逻辑搞对。再说递归的参数传递。这是重灾区。我当时学这道题的时候觉得左子树的先序右边界为什么是 preL leftSize而不是 preL 1 leftSize - 1 之类的被绕了很久。其实你只需要抓住一个事实左子树的节点个数是 leftSize 个这 leftSize 个节点在先序序列里是紧跟根节点之后、连续排列的。根的位置是 preL那么左子树范围就是从 preL 1 开始连续 leftSize 个节点所以左子树的先序右边界是 preL leftSize。对你没有看错不是 preL leftSize - 1因为左子树左边界是 preL 1个数是 leftSize所以右边界 左边界 个数 - 1 preL 1 leftSize - 1 preL leftSize。这块很多人容易硬记死记特别容易忘记悟透右边界 左边界 节点数 - 1这个公式之后再也不会搞错。右子树先序区间就更简单了左边界是 preL leftSize 1右边界直接是 preR。中序区间呢左子树中序左边界还是 inL右边界是 rootIdx - 1。右子树中序左边界是 rootIdx 1右边界是 inR。3.2 用一张表理清所有区间如果觉得上面的解释还是绕我干脆把各子树区间整理成一张表格你在代码里照着填就行子树先序左边界先序右边界中序左边界中序右边界根节点preLpreLrootIdxrootIdx左子树preL1preL leftSizeinLrootIdx-1右子树preL leftSize 1preRrootIdx1inR同样左子树的先序右边界也可以通过先序序列长度和中序序列长度必须相等这一点来验证。中序左子树长度是 rootIdx - inL也就是 leftSize。先序左子树长度是 (preL leftSize) - (preL 1) 1 leftSize。两边对上了。这个验证可以作为你自查的利器——只要发现两个区间长度不一致必然是下标算错了。3.3 哈希优化写法当树的节点数达到一定规模每次都用 for 循环找根会拖慢整体速度。我在天梯赛练习时经常遇到 n 在 10^4 到 10^5 的范围这时候 O(n^2) 确实有超时风险。优化办法也简单预先扫描一遍中序序列把每个字符和它的下标存进 unordered_mapunordered_mapchar, int pos; for (int i 0; i inorder.size(); i) { pos[inorder[i]] i; } TreeNode* build(vectorchar preorder, vectorchar inorder, int preL, int preR, int inL, int inR) { if (preL preR) return nullptr; char rootVal preorder[preL]; TreeNode* root new TreeNode(rootVal); int rootIdx pos[rootVal]; int leftSize rootIdx - inL; root-left build(preorder, inorder, preL 1, preL leftSize, inL, rootIdx - 1); root-right build(preorder, inorder, preL leftSize 1, preR, rootIdx 1, inR); return root; }hashmap 版本唯一要注意的是如果节点值可能重复哈希表存下标会出错。好在构造二叉树这类题默认节点值各不相同否则我们需要在每次递归时到中序区间内重新查找而不是直接哈希。实际做题时先看清题目有没有节点值互不相同这句话再决定用不用哈希。3.4 完整链路从建树到输出PTA 原题的完整流程通常是读入先序序列和中序序列构造二叉树然后层序遍历输出。我把完整的 C 代码贴在下面这里的层序遍历用队列实现这是树的 BFS 的标配#include iostream #include vector #include queue #include unordered_map using namespace std; struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; unordered_mapchar, int pos; TreeNode* build(vectorchar preorder, vectorchar inorder, int preL, int preR, int inL, int inR) { if (preL preR) return nullptr; char rootVal preorder[preL]; TreeNode* root new TreeNode(rootVal); int rootIdx pos[rootVal]; int leftSize rootIdx - inL; root-left build(preorder, inorder, preL 1, preL leftSize, inL, rootIdx - 1); root-right build(preorder, inorder, preL leftSize 1, preR, rootIdx 1, inR); return root; } void levelOrder(TreeNode* root) { if (!root) return; queueTreeNode* q; q.push(root); bool first true; while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (!first) cout ; cout node-val; first false; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } cout endl; } int main() { string a, b; cin a b; vectorchar preorder(a.begin(), a.end()); vectorchar inorder(b.begin(), b.end()); for (int i 0; i inorder.size(); i) { pos[inorder[i]] i; } TreeNode* root build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1); levelOrder(root); return 0; }这段代码是按字符读入的对应 PTA 常见的输入格式。如果要按整型读入把 vectorchar 换成 vectorint哈希表和 TreeNode 的 val 类型同步改动即可逻辑完全一样。编译器选 C17 或更新版本unordered_map 是标准库不需要额外安装任何东西。如果你用的是 C 语言需要自己写哈希或者每次查找时用循环扫描逻辑一样就是 O(n^2)。4. 写二叉树程序为什么总是报运行时错误我的完整排查链路我一度觉得这是全网最扎心的热搜词。因为它精准踩中了所有初学者的痛点。我自己第一次写这道题时也报过 runtime error当时在 PTA 上看着那一行红字整个人是懵的。现在回头看运行时错误基本逃不出下面这几类原因我把排查链路完整写出来。4.1 最常见的元凶递归出口写反或者压根没写这是最离谱但最常见的错误。有的同学递归函数开头写的不是 preL preR而是 preL preR 才返回结果单个节点时返回正常但一旦遇到空树就直接无限递归最终爆栈。递归出口必须覆盖空区间这个情况也就是左边界大于右边界而不是等于。一棵树的左子树为空我先序和中序区间自然就存在 preL preR 的情况出口写错程序必崩。我在调试时养成一个习惯递归函数一进来第一件事打印当前子树的范围和根值。比如cout build: pre [ preL , preR ], in [ inL , inR ] endl;一旦看到某个区间的 preL preR 还在递归肯定是出口写错。跑两步就能定位比干瞪眼强一百倍。4.2 数组越界下标计算错误引起的连锁崩塌我上面强调的右边界 左边界 节点数 - 1这个公式就是为你这里避坑的。如果 leftSize 算错一个单位先序右边界就会多一个或者少一个节点紧接着递归进入错误的区间越界访问几乎不可避免。举个例子如果你把左子树先序右边界写成 preL leftSize - 1那么左子树节点数就凭空少了 1 个。当 leftSize 原本为 1 时左边界 preL1 大于右边界 preL返回空但实际左子树应该有一个节点建树就建错了。这种错误不一定每次都报运行时错误有时能跑完但输出是错的。更麻烦。我建议你在递归函数入口加一个断言或者范围检查if (preL 0 || preR preorder.size() || inL 0 || inR inorder.size()) { // 说明下标算错了立刻终止方便定位 }实际提交时把断言去掉但调试阶段它真的能救命。4.3 内存问题new 出来的节点没有善后以及访问空指针还有一种运行时错误来自内存访问典型情况是访问了空指针的成员。比如层序遍历时没有判断节点是否为空就直接访问 node-val。再比如建树时左子树为空但递归返回了 nullptr后续操作前没有判空就会崩。另外如果题目要求多次构建二叉树每次都要记得释放内存否则程序挂掉或者内存超限也是运行时错误的一种表现。PTA 单次运行一般不会因为内存泄漏判错但要养成好习惯。4.4 递归爆栈当树退化成一条链这个场景虽然少见但值得一提。如果二叉树极度不平衡退化成一条链比如所有节点都只有右孩子递归深度会达到节点数 n。当 n 达到 10^5 甚至更高时函数调用栈可能撑不住表现为运行时错误而不是答案错误。遇到这种情况可以考虑用迭代法替代递归。不过 PTA 的这类构造二叉树题节点数通常控制在递归能承受的范围内这里仅作提醒。如果真的需要非递归版建树那就得用栈存状态逻辑复杂不少。我觉得除非题目数据量明确很大否则先用递归别自己吓自己。4.5 我的调试黄金法则我总结了一套排查运行时错误的固定套路每次遇到都能快速定位先看输入格式。PTA 的题目输入类型是字符串还是整数有没有空格读入方式对不对。字符串读入如果用了 cin int那铁定崩。再看递归出口。哪怕只有一行也要确认覆盖了空区间。然后打印每一层递归的区间和根值人工比对一次手算结果看哪一步开始区间不对劲。最后查空指针。所有需要访问的结构体成员前一步必须确定指针非空。这个方法看似笨但在调试构造二叉树这种递归程序时非常有效因为每一步的区间都是可预测的对照手算结果一眼就能发现偏差。5. 变形题与延伸会一道题不等于会一类题这道题做完只是起点。PTA 上很多题目看起来是新的本质上都是给定某个遍历序列构造或还原二叉树这一族问题的变体。把核心逻辑吃透之后这些变形题对你来说只是换汤不换药。5.1 后序中序构造二叉树这是最常见的变体。后序遍历顺序是左子树、右子树、根所以后序序列的最后一个元素是整棵树的根。在中序里找到根的位置左边是左子树右边是右子树。核心区别仅仅在于根的位置从先序的最左边变成了后序的最右边。递归代码几乎一样只是取根要用后序的右边界而不是左边界。对应地处理左子树时后序区间的右边界要小心移动。以后序中序为例假设后序区间是 [postL, postR]根是 postR左子树节点数是 leftSize则左子树后序区间是 [postL, postL leftSize - 1]右子树后序区间是 [postL leftSize, postR - 1]。如果你直接把先序版本的下标逻辑搬过来一定会错因为先序和后序的读取方向不同。我建议你重新按右边界 左边界 节点数 - 1这个公式推一遍而不是硬记。5.2 先序后序能构造二叉树吗前面已经说了答案是不能唯一确定。原因是当一棵子树只有一个孩子时这个孩子到底是左孩子还是右孩子先序和后序给不出任何线索。举个例子先序是 AB后序是 BA这棵树的根是 AB 可能是 A 的左孩子也可能是 A 的右孩子。单凭这两个序列你根本分不出来。考试喜欢考这种判断题做题时要有底气。5.3 中序序列任意一个显式根的序列都能构造其实只要有一个序列能确定谁是根再配合中序切分左右子树就能递归构造二叉树。先序和后序都能指示根的位置所以它们的组合都能用于唯一构造后序先序不能因为它俩都能指示根但无法区分左右孩子归属。有些题目给的是层序序列中序序列层序也能在某棵子树中确定根的位置处理方式略有不同但核心思路一致找到根用中序切左右递归解决。5.4 重建树之后的其他操作建树只是手段不是目的。PTA 上常见的配套操作包括层序遍历也就是前面代码里已经实现的 levelOrder求树的高度判断是否完全二叉树以及输出根到叶子的路径。这些操作的基础都是树已经建好。所以建树这步的稳定性直接决定你后面所有操作的正确性。我每次做完建树题之后都会顺手写一个输出层序的函数验证因为层序是最直观、最容易和手算结果比对的序列。一旦层序和你推导的一致树基本就是对的。6. 最后聊点实际的题目刷到这一步接下来怎么练这道题在 PTA 上的定位其实是树与二叉树专题的入门到中等过渡题。过了这道题后面会遇到线索二叉树、哈夫曼树、二叉搜索树、AVL 树等等。我的建议是趁这个机会把几样基础能力一次性补齐。第一递归思想不要只停留在能写的层面要能讲清楚。你能不能拿一支笔画一个随机二叉树然后现场写出它的先序、中序、后序、层序并且在纸上走一遍递归建树过程如果能这道题你就彻底通了。第二数组下标推算能力要练成肌肉记忆。下次遇到任意类似的区间拆分问题一律套公式区间长度 右边界 - 左边界 1并且用先序区间长度 中序区间长度去验证每一步的拆分是否正确。我见过很多人为了省这个验证步骤浪费了更多调试时间。第三内存管理意识从这道题就该养成。每次 new 出的节点最后是不是都 delete 了如果不 delete程序多次建树时会不会内存爆掉这种意识到了后面写更复杂的数据结构时会帮你少踩很多坑。如果你想要更多的练习变体我推荐你自己改几个方向去写把先序中序改成后序中序把字符节点改成整数节点把递归改成非递归把输出层序改成输出后序。每改一个方向你对这个知识点的理解就深一层。把这些方向都刷完你就不是会一道题而是会一类题。最后分享一个我自己练题时的小习惯我会把每次做错的题和卡住的知识点单独记在一个文档里标注出是下标算错、入口写错还是思路不清。过段时间再回来看一眼进步非常明显。希望这篇复盘对你也有同样的帮助。