这道“信息学奥赛一本通1304扩展二叉树”我印象很深。当年我刷到这一题的时候正好是学树结构最迷糊的阶段课本上二叉树遍历讲得头头是道一到写程序就不知道递归该怎么返回更别提用一串带点的先序序列去还原一棵树了。后来把这道题弄明白才真正感觉到“指针递归”这组合没那么吓人。如果你是正在刷一本通的朋友或者刚接触二叉树、准备CSP/NOIP这篇内容应该能帮你少走不少弯路。题目本身不复杂核心就一件事给你一棵二叉树的“扩展先序遍历序列”例如ABD..E..C..其中.表示空子树你要据此把二叉树建出来然后输出它的中序遍历和后序遍历。很多同学拿到题第一反应是“这不就是先序遍历输入吗直接建树不就行了”但真正动手才会发现坑全藏在递归边界、字符串下标、空指针这些细节里。1. 题目描述与考点拆解1.1 原题到底让你干什么一本通1304这道题题面一般是这样描述的输入一个字符串它是一棵二叉树的扩展先序序列空节点用.表示请你输出这棵二叉树的中序序列和后序序列。举个例子输入为ABD..E..C..对应的一棵二叉树是A / \ B C / \ D E输出应该是中序DBEA C具体格式看题目要求一般是每个节点后跟一个空格或直接连续 后序DEB C A这里有几个容易忽略的点需要注意。第一给出的序列一定是“先序遍历”的结果也就是“根、左子树、右子树”的顺序。第二序列中每个空节点都要用.显式标记出来这样才能唯一确定树的结构。第三题目要求你建树后再输出而不是直接通过某种规律从字符串里硬凑出中序后序序列所以建树这个环节逃不掉。1.2 隐藏的知识点清单这道题虽然看起来只是一个建树遍历的练习但真正考到的知识点其实有好几个二叉树的先序遍历递归实现先根、再左、再右这是建树时读取字符的顺序依据。递归终止条件的判断遇到.代表空子树此时不能继续递归必须返回空指针或空节点编号。字符串游标索引的处理方式递归建树时必须让所有递归层次共享同一个“当前读到哪里”的计数器否则会读乱。中序和后序遍历的递归写法换一下访问节点的顺序就能实现但很多人会在这里把visit的位置放错。C指针或引用传参这是新手最容易崩溃的地方后面我会单独展开。换句话说这道题表面上是一个“建树题”实际上是在检验你对递归执行过程的理解深度。如果你只是背代码很难应对题目把.换成#、把先序换成后序这类小变体。2. 为什么叫“扩展二叉树”2.1 普通二叉树序列的局限先思考一个问题给你一个先序遍历序列ABC你能还原出唯一的二叉树吗显然不能。因为ABC既可以是左斜树A \ B \ C也可以是右斜树A / B / C甚至可以是根节点A的左子树是B、B的左子树是C或者根节点A的右子树是B、B的右子树是C……在没有空节点标记的情况下先序遍历丢失了“哪里是空”的信息所以树结构不唯一。同理单独的“中序序列”或者“后序序列”也不能唯一确定一棵二叉树。通常我们需要“先序中序”或“后序中序”才能还原一棵树。而扩展二叉树就是解决这个问题的方案之一在遍历时把空子树显式地用一个特殊符号题目里通常是.写出来这样连空位都保留了下来整棵树的结构信息就完整了。2.2 扩展序列的生成规则所谓“扩展二叉树”可以理解成把一棵普通二叉树的所有空子树都补上一个“虚拟叶子节点”。比如上面那棵A(B(D,E),C)的二叉树它的扩展先序遍历过程是访问根节点A输出A。遍历左子树先访问B输出B。遍历B的左子树先访问D输出D。遍历D的左子树空输出.。遍历D的右子树空输出.。回到B遍历B的右子树先访问E输出E。遍历E的左子树空输出.。遍历E的右子树空输出.。回到A遍历A的右子树先访问C输出C。遍历C的左子树空输出.。遍历C的右子树空输出.。最终得到的字符串就是ABD..E..C..。可以看到每个非空节点后面都“跟着”两个空标记除非它的子树非空但最终每个叶子节点后面都会有.。反过来从这样一串序列我们就能一步一步还原出唯一的二叉树。2.3 用生活化的方式来理解“占位符”你可以把扩展二叉树想象成一份“带空格的表格”。假设你要记录一个公司每层楼的工位分布普通表格只记录有人的工位编号那么你就不知道某个空位是在哪一排的哪个位置但如果把空位也标记成“空”整张表格就完整了任何人拿到这张表都能把工位还原出来。在二叉树里.就是那个“空位占位符”。它告诉递归程序这里没有左孩子了不要再往下了或者这里没有右孩子了结束这一支的递归。正因为有了这样的占位符信息才不会丢失。3. 核心思路递归建树3.1 从先序序列重建的递归模型现在给定扩展先序序列S我们要把它还原成链式存储的二叉树。递归的思考方式非常简单当前读到一个字符ch。如果ch是.说明当前位置是空节点直接返回NULL空指针。如果ch不是.说明这是一个真实节点创建一个新节点把ch存进data域。然后递归构建左子树递归构建右子树。返回当前节点指针。这个递归过程严格遵循先序遍历的“根、左、右”顺序。关键在于每一步递归都要知道“现在应该从字符串的哪个位置开始读”。如果每次递归都能自动往后移动一个字符整个建树过程就能一气呵成。3.2 为什么必须用索引引用或全局变量很多刚开始写这道题的同学会写出下面这样的建树函数Node* build(string s) { int idx 0; if (s[idx] .) return NULL; Node* root new Node(s[idx]); idx; root-left build(s); root-right build(s); return root; }这段代码的问题很明显idx只在每次函数调用的最开始被赋值为0而且没有传递给子递归。结果就是每次递归都从字符串的第0个字符开始读永远读不出后续字符最后必然栈溢出或建出错误结构。正确的做法有两种方法一把索引定义成全局变量。int idx 0; Node* build(string s) { char ch s[idx]; if (ch .) return NULL; Node* root new Node(ch); root-left build(s); root-right build(s); return root; }方法二用引用传递索引。Node* build(string s, int idx) { char ch s[idx]; if (ch .) return NULL; Node* root new Node(ch); root-left build(s, idx); root-right build(s, idx); return root; }两种方法本质都一样所有递归调用共享同一个游标。每次读取一个字符后游标就后移一位不会因为递归层数深而丢失位置。这里我强烈推荐“引用传递”的方式因为全局变量在复杂工程里容易引起“命名污染”而在竞赛代码里虽然关系不大但写成引用能让你更清楚地看到数据流向。当然只要代码写得严谨两种都能AC。3.3 递归终止条件与返回值类型这个递归的终止条件有两个层次遇到.当前子树为空返回NULL。遇到字符串末尾严格来说一个合法输入不会出现“该读字符时却没字符”的情况因为每个.都对应一个空位置所有非空节点都有两个孩子或空孩子所以整个字符串读完时整棵树正好建完。但为了程序健壮性你可以在函数开头判断if (idx s.size()) return NULL;防止读越界。返回值类型是节点指针Node*。如果是空节点返回NULL如果是非空节点就返回指向新建节点的指针。调用方父节点拿到这个指针后把它挂到自己的left或right上。这个“回调”的过程正是递归建树的精髓子问题解决了把结果交还给上一层。4. 完整代码实现与逐段注释4.1 节点结构体定义先定义二叉树的节点#include iostream #include string using namespace std; struct Node { char data; // 节点存储的字符 Node* left; // 左孩子指针 Node* right; // 右孩子指针 Node(char c) : data(c), left(NULL), right(NULL) {} };这里我用构造函数Node(char c)来初始化节点让代码更干净。left和right一开始都指向NULL后面建树时再赋值。4.2 建树函数实现// 递归建树idx是当前读取位置引用传递 Node* buildTree(const string s, int idx) { if (idx s.size()) return NULL; // 防止越界合法数据一般不会触发 char ch s[idx]; // 读取一个字符并让游标后移 if (ch .) return NULL; // 空节点 Node* root new Node(ch); // 创建根节点 root-left buildTree(s, idx); // 递归构建左子树 root-right buildTree(s, idx); // 递归构建右子树 return root; }注意这里ch是我们从字符串中取出来的字符如果它是.就直接返回空指针之后父节点会把NULL赋给孩子。这不影响游标的位置因为.也是消耗掉了一个字符。4.3 中序和后序遍历void inorder(Node* root) { if (root NULL) return; inorder(root-left); cout root-data; // 输出节点 inorder(root-right); } void postorder(Node* root) { if (root NULL) return; postorder(root-left); postorder(root-right); cout root-data; }中序遍历的顺序是“左、根、右”后序遍历是“左、右、根”。你只需要记住cout root-data这个输出语句放在递归调用的前面、中间、后面就分别对应先序、中序、后序。理解了这个遍历代码就不需要死记硬背。4.4 主函数与输入输出格式题目一般要求输出中序和后序序列每个节点输出后可能有空格也可能没有具体看题目的输出格式。这里我按常见的“字符之间无空格”来写你也可以根据题目要求调整。int main() { string s; cin s; int idx 0; Node* root buildTree(s, idx); inorder(root); cout endl; postorder(root); cout endl; return 0; }如果你的题目要求输出“每个节点后面跟一个空格”就把cout root-data改成cout root-data 。注意判断题目是“行末无多余空格”还是“允许多余空格”这个小细节决定了你是不是会PEPresentation Error。完整合起来的代码大概30行非常精简。我第一次写完整运行通过后心里只有一个感觉原来递归建树可以这么漂亮。5. 调试经验为什么总是报运行时错误5.1 经典错误一递归索引不前进这个问题我在3.2里已经举过例子。如果你在调试时发现程序跑着跑着就“栈溢出”了或者建出来的树结构完全不对十有八九是索引没有正确共享。我见过不少同学把idx作为参数按值传递结果每次递归都从0开始程序死循环最后报Process exited with code -1073741571之类的错误。排查方法很简单在buildTree函数开头打印idx和ch看看字符读取顺序是不是和字符串一样。如果发现一直打印第一个字符那就肯定是传参方式有问题。5.2 经典错误二访问空指针另一个高频错误是在遍历时没有判断root NULL直接访问root-left结果程序在运行时崩溃报“Segmentation fault”或者“Null pointer dereference”。很多新手都知道要判断但写的时候会漏。比如有人这样写中序遍历void inorder(Node* root) { if (root NULL) return; inorder(root-left); cout root-data; inorder(root-right); }这是对的。但如果写成了if (root-left NULL) return;就完蛋了——因为根节点的左子树可能是空但根节点本身非空直接访问root-left在必然存在根节点时没问题可一旦某个递归层拿到的root本身就是NULL再访问root-left就崩溃了。所以一定要记住任何指针在使用之前先检查它是否为NULL。这不是“小心过度”而是写树结构的铁律。5.3 经典错误三字符串下标越界C字符串访问s[idx]时如果idx超出size()结果是未定义行为。有些编译器可能什么都不报但程序输出的中序、后序会多出一些奇怪的字符。原因是递归读字符时没有判断“是否读到末尾”。正常输入下每个.都对应空位序列本身是完整的递归会在遇到.后返回不会越界。但如果你手动测试的字符串不合法比如少了几个.递归就会试图读取字符串之外的内容。解决办法在buildTree开头加一行if (idx s.size()) return NULL;这行代码看似多余却能让你在调试错误数据时避免读到随机内存得到更清晰的表现。正式评测时合法数据不会触发这条分支所以不影响正确性。5.4 经典错误四把“输入”和“输出”搞混有的题目输入是一个字符串直接cin s就能读入。但如果字符串中包含空格或换行你就需要用getline(cin, s)来读。扩展二叉树序列里只有字母和.一般没有空格所以cin s足够。不过在一些变体题中节点可能是多个字符比如“apple”“banana”这时候就需要用分隔符隔开用while (cin token)的方式读。我在做题时习惯先看一眼题目给的样例输入里有没有空格再决定怎么读。这个细节看起来小却直接影响你能不能AC。5.5 调试技巧用先序遍历反推每当你建完树后不确定结构对不对有个非常直观的验证方式把建好的树再做一次先序遍历如果输出结果和原始输入字符串去掉.后完全相同那基本可以确认建树逻辑没错。另外你也可以在buildTree里打印每次读取的字符和当前idxcerr idx idx ch ch endl;这样你就能一步步看到递归的走向。我当年就是这样定位到“索引没有引用传递”这个问题的。6. 题目变体与扩展应用6.1 根据扩展后序序列建树有些题目会给出扩展后序序列比如..D..E.B..C.A要求还原二叉树。思路类似只是递归顺序变成了“左、右、根”。你可以从字符串末尾往前读取先读到的就是根节点然后递归建右子树再递归建左子树。建立后序扩展序列建树的递归框架是这样的Node* buildPost(const string s, int idx) { if (idx 0) return NULL; char ch s[idx--]; if (ch .) return NULL; Node* root new Node(ch); root-right buildPost(s, idx); // 注意先右后左 root-left buildPost(s, idx); return root; }这里有一个容易踩的坑后序序列建树时递归建完右子树再建左子树顺序不能反。因为输出序列是“左、右、根”反过来读的时候先遇到的是根其次是右子树的序列最后才是左子树的序列所以要先处理右子树。6.2 层次遍历扩展序列建树扩展序列不一定是先序也可能是“层次扩展序列”就是一排一排地给出节点空节点用.代替。比如ABC..D..可以表示根A左孩子B右孩子CB的左孩子空B的右孩子空C的左孩子DC的右孩子空。这种建树方式用队列广度优先实现和先序建树完全不同。用队列建层次扩展树的思路是先把根节点入队然后逐个读取后续字符创建节点并挂到当前队首的左右孩子上每挂一个孩子就把新节点入队。当队首节点的左右孩子都挂满后队首出队继续处理下一个节点。这个变体虽然不常考但如果你理解了先序扩展建树再去看层次扩展建树会更清楚“扩展标记”这个通用思路的价值。6.3 顺便求树的深度、叶子数有时题目不直接要求中序后序而是问深度、叶子数、复制一棵树等。在完成建树后这些都可以通过额外的递归函数实现。比如求深度int depth(Node* root) { if (root NULL) return 0; int leftDepth depth(root-left); int rightDepth depth(root-right); return max(leftDepth, rightDepth) 1; }求叶子数int leafCount(Node* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return leafCount(root-left) leafCount(root-right); }这些其实都是基本的递归分治但把它们一起练习能帮你建立“树上递归”的直觉。6.4 扩展二叉树与“序列化/反序列化”的关系如果你以后接触LeetCode会发现有一道经典题叫“二叉树的序列化与反序列化”Serialization and Deserialization of Binary Tree。它做的事情就是把一棵二叉树转换成一个字符串再通过这个字符串还原二叉树。很多解法使用的正是“先序扩展序列”空节点用#或null标记。这和1304题的思路完全一致只是字符和语言不同。所以你可以把这道一本通题目当成一个基础版“序列化”练手题。搞懂了它以后遇到面试题里的重建二叉树会轻松很多。有些进阶题目还会要求你把树保存到文件里再读取出来原理也一样用扩展标记保住结构信息。7. 个人小结与继续刷题建议在刷一本通的过程中1304这道题给我的收获不仅仅是“会写代码”而已而是真正理解了递归与全局状态之间的关系。以前我总觉得递归是一个“黑魔法”看别人代码能看懂自己一写就废。直到这道题逼着我去确认“idx到底是怎么在递归层之间传递的”我才发现递归不过是一个不断压栈、不停返回的过程。当你把“每层递归需要什么状态、返回什么状态”想明白递归代码就变得顺理成章。对还在纠结这道题的朋友我的建议是第一不要只看别人的代码一定要自己动手画一画递归调用过程。随便取一个个例比如AB..C..在纸上模拟一遍buildTree的调用栈把每次idx的值和读到的字符写出来整个过程会清晰很多。第二如果报了运行时错误优先检查空指针和索引传递。这个题的“运行时错误”绝大多数源于这些基础问题而不是算法思路。第三做完这道题可以顺手把关于二叉树遍历的其它题——比如已知前序中序求后序、已知后序中序求前序、求解二叉树深度——都在一本通里找出来一起刷。它们之间是层层递进的关系串在一起理解效率比自己一个题一个题瞎碰高得多。最后再分享一个小技巧在自己测试的时候可以专门测试只有一个节点的序列比如A..以及整棵树是左斜树的序列比如A.B..或AB...看看输出是否符合预期。这些极端小数据往往能暴露出代码里隐藏的边界问题我在实际做题时靠这个方法省了不少调试时间。