刷过《信息学奥赛一本通》的同学对1304这道“扩展二叉树”应该都不陌生。题面很短输入一串带空标记的先序序列让你把二叉树重建出来再输出中序和后序遍历。看着简单真正动手时很多人在建树这一步就卡住了递归返回不对、索引没有推进、程序一跑就崩。这题表面上是考建树和遍历实际上是考你对递归过程和指针传递的理解。本文就围绕这道题把扩展二叉树的前因后果、建树原理、完整代码和调试心得一次讲透适合正在备战信息学奥赛、刚学二叉树数据结构以及被各种“运行时错误”折磨的读者。1. 先把题目看清楚扩展二叉树到底在考什么1.1 题面还原与样例输入题目会给出一棵二叉树的“扩展先序遍历序列”。所谓扩展就是把原来的空指针也用一个可见字符表达出来比如英文句点.也可能用#。信息学奥赛一本通这一题习惯用.表示空节点。例如输入序列ABD..EH...CF..G..这个序列对应的树结构是A / \ B C / \ / \ D E F G / H注意看序列的读法A是根然后B是A的左子树根接着D是B的左子树根D后面的两个.分别表示D的左儿子和右儿子都为空D结束。再读E它是B的右子树根E后面跟着H和两个.说明H是E的左儿子且H是叶子再一个.表示E的右儿子为空。继续往后C是A的右子树根F是C的左儿子且叶子G是C的右儿子且叶子。题目要求输出这棵树的中序遍历序列和后序遍历序列。对上面这个例子中序DBHEAFCG 后序DHEBFGCA我第一次看到这个输出时还专门对着树画了一遍确认顺序没错。所以这道题的核心任务就三步读入扩展先序序列按序列建出二叉树然后递归输出中序和后序。1.2 为什么普通先序序列不够用有人会问直接用普通先序遍历不也能建树吗还真不能。先序序列AB既可以表示A的左儿子是B也可以表示A的右儿子是B两种情况先序序列完全一样。但加上空节点标记后AB...和A.B.就能区分这两种结构了。扩展二叉树相当于把原本隐藏的空指针全部显式化让序列中每个节点的左子树和右子树都有明确边界。可以打个比方普通先序像是快递单上只写了“经过客厅到卧室”但没写哪一层哪一户扩展先序则把每一处拐弯、每一扇不会打开的门都标了出来照着走就绝对不会迷路。这也是为什么只有“带空标记的先序序列”这一个序列就能唯一还原二叉树而单独的中序或后序都不行。2. 核心思路用扩展先序递归还原二叉树2.1 递归建树的本质扩展先序序列的递归特性非常明显第一个字符一定是根节点根节点之后从第二个字符开始的一整块是左子树的扩展先序直到左子树完全结束再往后才是右子树的扩展先序。这个“一整块”到底有多长没法提前算出来只能递归去消费。所以建树函数可以设计成每次读取一个字符如果是.就返回空指针如果不是.就创建一个节点然后递归构建左子树再递归构建右子树。递归天然地帮我们完成了“切分块”的工作。以ABD..EH...CF..G..为例第一步读A创建根节点A。递归建A的左子树从剩余的第一个字符B开始。B的左子树读DD的左右都是.于是D的两个子树返回空D子树结束。继续建B的右子树读EE的左子树读HH的两个儿子都是空然后读E的右儿子为空E子树结束。此时A的左子树全部构建完毕继续读C进入A的右子树……这个过程中每个节点都在“先处理自己、再处理左边、最后处理右边”和先序遍历的顺序完全一致。建树函数本身几乎就是先序遍历的“翻版”区别只是遇到.时不再创建节点而已。2.2 索引参数为什么必须用引用写建树函数时最容易出错的是字符串索引的传递。我用的是这样的签名Node* build(const string s, int idx)注意这里idx必须是引用或者声明成全局变量。如果用普通值传递每个递归层都拿到同一个idx遇到.返回后外层索引没有变化会导致反复读取同一个字符最终陷入死递归程序栈溢出报错。我见过很多初学者的代码是这样写的Node* build(string s, int idx) // 错误示范idx按值传这样建树时左子树递归确实会返回但是回到本层后idx仍然是原来的值再建右子树时可能又从头开始读整个树形就全乱了。记住一句话递归过程中需要“消费”输入序列消费进度必须共享。引用和全局变量都能做到我更推荐用引用函数接口清晰不会和主函数的其他全局状态冲突。2.3 中序和后序遍历还是那套递归模板建树之后遍历就是纯粹的递归输出。中序是左、根、右后序是左、右、根。代码模板固定唯一要留意的是递归终止条件——节点为空就返回不要访问空指针的左右孩子。这两个函数我建议直接背下来因为信息学奥赛里大量题目都用到遍历框架。很多同学会混淆中序和后序其实只要抓住“根的位置”就行中序的根在中间后序的根在最后。写代码时先想清楚当前节点什么时候输出再决定递归调用的顺序。3. 完整代码实现从建树到遍历一次过3.1 结构体定义与函数划分用C手写二叉树可以定义一个结构体struct Node { char data; Node *left, *right; Node(char c) : data(c), left(nullptr), right(nullptr) {} };构造函数里把左右指针初始化为空这是一个很好的习惯。很多运行时错误就是因为新建节点后左右指针没有初始化就访问了导致野指针崩溃。代码最好拆成四个函数build根据扩展先序字符串建树。inorder中序遍历。postorder后序遍历。可选destroy释放整棵树的内存。竞赛里不释放内存也不会被判错但如果你在本地反复测试多组数据建议写一个释放函数避免内存占用越来越高。3.2 建树函数逐行解读把建树函数单独拿出来看Node* build(const string s, int idx) { if (idx s.size()) return nullptr; char ch s[idx]; if (ch .) return nullptr; Node* root new Node(ch); root-left build(s, idx); root-right build(s, idx); return root; }第一行判断idx s.size()是防御性写法。正常情况下输入序列结束时正好所有子树都返回空不会越界但加上这个判断能避免一些边界样例导致崩溃。第二行char ch s[idx];要特别注意这里先取字符然后索引加一。如果写成s[idx]等价于先用后加是对的。但有人喜欢写成char ch s[idx]; idx;效果一样两种写法都可以。切记不要写char ch s[idx];那是先加再用会跳过一个字符。当ch .时返回空指针这个分支是整棵树递归的“刹车”。没有这个分支递归会一直读下去直到越界。如果当前字符是正常字母就创建根节点接着递归建左子树、右子树。这里有一个很关键的点build(s, idx)调用左子树时会从左子树的开头一直处理到左子树的结束位置等左子树调用返回idx已经停在右子树序列的起点。所以紧接着调右子树就好不需要手动计算右子树从哪里开始。这正是前面坚持用引用的原因。3.3 遍历输出细节中序和后序函数不需要返回值直接输出字符即可void inorder(Node* root) { if (root nullptr) return; inorder(root-left); cout root-data; inorder(root-right); } void postorder(Node* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-data; }注意输出不要加空格。有些题要求每个字符占一行有些要求连续字符串一定要看题目的输出格式要求。一本通1304的要求是直接输出两行一行中序一行后序所以这里用cout root-data不换行最后在函数外面统一cout endl。3.4 完整可直接运行的C代码下面给出一个能直接跑通样例的完整程序。我是按多组输入直到EOF写的赛场上很常见。#include iostream #include string using namespace std; struct Node { char data; Node *left, *right; Node(char c) : data(c), left(nullptr), right(nullptr) {} }; Node* build(const string s, int idx) { if (idx (int)s.size()) return nullptr; char ch s[idx]; if (ch .) return nullptr; Node* root new Node(ch); root-left build(s, idx); root-right build(s, idx); return root; } void inorder(Node* root) { if (root nullptr) return; inorder(root-left); cout root-data; inorder(root-right); } void postorder(Node* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-data; } void destroy(Node* root) { if (root nullptr) return; destroy(root-left); destroy(root-right); delete root; } int main() { string s; while (cin s) { int idx 0; Node* root build(s, idx); inorder(root); cout endl; postorder(root); cout endl; destroy(root); } return 0; }我用输入ABD..EH...CF..G..测试输出DBHEAFCG DHEBFGCA和题目样例吻合。如果题目只给单组输入把while (cin s)改成cin s就行。4. 写二叉树程序为什么总是报运行时错误避坑与调试实录4.1 最常见的五个坑与对应解法很多人在信息学奥赛OJ上提交这题编译通过但一运行就Segmentation Fault。我归纳了五个高频原因。第一递归时索引没有正确更新。前面说过使用按值传递的索引或者忘记idx都会导致递归无限循环或重复读字符。解决办法是使用引用或全局索引并且在读字符后立即自增。第二访问空指针的左右孩子。inorder和postorder函数开头如果没有判断root nullptr当遍历到空节点时会尝试访问root-left直接崩溃。这是二叉树题目的头号杀手递归函数一进来第一件事就应该判空。第三用了char数组但字符串长度不确定越界读入。如果你用scanf(%s, str)不会读入空格但如果题目的空节点用空格表示就会出问题。解决方法是使用string配合cin避免长度问题。第四树退化成链导致递归栈溢出。如果输入序列构造出的树深度特别大递归层数可能超过系统栈大小。信息学奥赛题目一般不会给极端链状数据但如果你在本BT构造深度为10万的树测试就需要改写成非递归。不过1304这题默认不会这么刁钻。第五多组输入时忘记重置索引或释放内存。idx在每次新序列建树前必须重新赋值为0否则上一组数据的位置会带到下一组。释放内存可以避免累计内存增长尤其是循环测试大量数据时。4.2 我常用的调试三板斧遇到建树问题我习惯在纸上模拟一遍递归过程或者在代码中临时打印日志。具体方法是在build函数中加一条调试输出打印当前读取到的字符和索引位置。cout 读到 ch 当前idx idx endl;通过日志可以看到递归是否按预期顺序读入字符。如果是A、B、D、.、.、E……说明正常如果出现反复读A那就说明索引没更新。第二板斧是在遍历函数里打印“进入节点”的信息确认树的形状是否和预期一致。比如在建树完成后临时写一个先序遍历输出看看是否等于原输入序列。如果建出的树先序遍历结果和输入字符串一致说明建树成功。第三板斧是在本地IDE里一步一步调试在build函数调用root-left build(s, idx);这行打上断点查看idx的变化。特别是第一次写递归的同学建议用调试器跟一遍ABD..这个过程递归就不再神秘。4.3 常见问题速查表现象可能原因解决方案程序运行后直接崩溃访问了空指针的成员递归函数开头判空输出结果缺失或乱序递归索引没有正确共享使用引用或全局变量重复建出一样的子树字符自增位置写错检查idx的位置处理多组数据时结果串串每组开始时没有重置索引循环内将idx0输入含空格导致读取失败使用了cin或scanf(%s)改用getline或换掉空格标记极端数据栈溢出递归深度过大改非递归建树/遍历这张表不仅适用于1304在后面做其他二叉树题目时也能套用。只要遇到“二叉树程序报运行时错误”先按这几项排查至少能解决九成问题。5. 从一道题到一类题扩展二叉树的变式与延伸5.1 顺手求深度、节点数、叶子数扩展先序序列建好的树可以当普通二叉树用因此各种统计问题都能接上。比如求二叉树深度代码很简单int depth(Node* root) { if (root nullptr) return 0; return max(depth(root-left), depth(root-right)) 1; }求节点总数就是左右子树节点数之和加1求叶子数就是左右子树都为空时返回1。这些变式在信息学奥赛的树形DP入门中很常见。理解递归时可以把“整棵树的深度”拆成“左子树深度”和“右子树深度”的较大值再加根节点这一层。5.2 层次遍历怎么做扩展先序建树只能得到先序序列但树的层次结构也隐含在里面。层次遍历需要配合队列void levelOrder(Node* root) { if (root nullptr) return; queueNode* q; q.push(root); while (!q.empty()) { Node* cur q.front(); q.pop(); cout cur-data; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }层序遍历是BFS的经典应用很多题目会要求输出每层节点或者判断是否是完全二叉树。有了建好的树这些操作都只是模板套用。5.3 用数组模拟指针避开new的开销在个别内存紧张或追求速度的题目里动态new节点不是最优选择。可以用静态数组模拟二叉树const int MAXN 10005; char val[MAXN]; int lch[MAXN], rch[MAXN]; int cnt 0; int build(const string s, int idx) { if (idx s.size()) return 0; char ch s[idx]; if (ch .) return 0; int cur cnt; val[cur] ch; lch[cur] build(s, idx); rch[cur] build(s, idx); return cur; }这里用0表示空节点用数组下标作为指针。优点是没有动态内存分配不会泄漏调试时还能直接看数组内容。信息学奥赛中有很多题目用这种静态写法更稳妥尤其是一次建多棵树或者树节点很多时。5.4 与其他建树方式对比扩展先序是“唯一单序列建树”的特例。除此之外常见的建树组合还有先序中序、后序中序。为什么中序必须配合另一个序列因为中序只能确定左右孩子的相对顺序但无法确定根是谁先序或后序能确定根但无法划分左右子树。两者结合才能还原二叉树。对比一下思路先序中序先序第一个字符是根在中序里找到根的位置左边是左子树中序右边是右子树中序再根据长度在先序中切出左右子树的先序。后序中序后序最后一个字符是根其余思路相同。扩展先序空节点已经帮我们划好了左右子树的边界递归时不需要再查中序只用消费一个序列。理解这三种方式可以帮你把树结构的递归逻辑串起来。扩展二叉树是其中最直观、最容易上手的一个。最后再分享一点个人体会我做这题时最大的收获不是背会了建树代码而是彻底理解了“递归消费输入”这件事。很多同学写二叉树程序总觉得递归很玄其实只要抓住两个东西终止条件和子问题拆分。扩展二叉树恰好把这两点展现得非常清楚——遇到空节点终止一个完整节点加左右子树递归就是子问题拆分。如果你正在刷《信息学奥赛一本通》建议不要直接抄代码先自己在纸上把ABD..EH...CF..G..这个序列的建树过程走一遍再动手写。写错几次也没关系用调试器跟一遍比看十遍题解都管用。这道题的价值绝不仅仅是一道水题它后面的递归思想会一直跟着你走到树形DP、线段树、平衡树早一天想通后面就轻松一天。
刷过《信息学奥赛一本通》的同学对1304这道“扩展二叉树”应该都不陌生。题面很短输入一串带空标记的先序序列让你把二叉树重建出来再输出中序和后序遍历。看着简单真正动手时很多人在建树这一步就卡住了递归返回不对、索引没有推进、程序一跑就崩。这题表面上是考建树和遍历实际上是考你对递归过程和指针传递的理解。本文就围绕这道题把扩展二叉树的前因后果、建树原理、完整代码和调试心得一次讲透适合正在备战信息学奥赛、刚学二叉树数据结构以及被各种“运行时错误”折磨的读者。1. 先把题目看清楚扩展二叉树到底在考什么1.1 题面还原与样例输入题目会给出一棵二叉树的“扩展先序遍历序列”。所谓扩展就是把原来的空指针也用一个可见字符表达出来比如英文句点.也可能用#。信息学奥赛一本通这一题习惯用.表示空节点。例如输入序列ABD..EH...CF..G..这个序列对应的树结构是A / \ B C / \ / \ D E F G / H注意看序列的读法A是根然后B是A的左子树根接着D是B的左子树根D后面的两个.分别表示D的左儿子和右儿子都为空D结束。再读E它是B的右子树根E后面跟着H和两个.说明H是E的左儿子且H是叶子再一个.表示E的右儿子为空。继续往后C是A的右子树根F是C的左儿子且叶子G是C的右儿子且叶子。题目要求输出这棵树的中序遍历序列和后序遍历序列。对上面这个例子中序DBHEAFCG 后序DHEBFGCA我第一次看到这个输出时还专门对着树画了一遍确认顺序没错。所以这道题的核心任务就三步读入扩展先序序列按序列建出二叉树然后递归输出中序和后序。1.2 为什么普通先序序列不够用有人会问直接用普通先序遍历不也能建树吗还真不能。先序序列AB既可以表示A的左儿子是B也可以表示A的右儿子是B两种情况先序序列完全一样。但加上空节点标记后AB...和A.B.就能区分这两种结构了。扩展二叉树相当于把原本隐藏的空指针全部显式化让序列中每个节点的左子树和右子树都有明确边界。可以打个比方普通先序像是快递单上只写了“经过客厅到卧室”但没写哪一层哪一户扩展先序则把每一处拐弯、每一扇不会打开的门都标了出来照着走就绝对不会迷路。这也是为什么只有“带空标记的先序序列”这一个序列就能唯一还原二叉树而单独的中序或后序都不行。2. 核心思路用扩展先序递归还原二叉树2.1 递归建树的本质扩展先序序列的递归特性非常明显第一个字符一定是根节点根节点之后从第二个字符开始的一整块是左子树的扩展先序直到左子树完全结束再往后才是右子树的扩展先序。这个“一整块”到底有多长没法提前算出来只能递归去消费。所以建树函数可以设计成每次读取一个字符如果是.就返回空指针如果不是.就创建一个节点然后递归构建左子树再递归构建右子树。递归天然地帮我们完成了“切分块”的工作。以ABD..EH...CF..G..为例第一步读A创建根节点A。递归建A的左子树从剩余的第一个字符B开始。B的左子树读DD的左右都是.于是D的两个子树返回空D子树结束。继续建B的右子树读EE的左子树读HH的两个儿子都是空然后读E的右儿子为空E子树结束。此时A的左子树全部构建完毕继续读C进入A的右子树……这个过程中每个节点都在“先处理自己、再处理左边、最后处理右边”和先序遍历的顺序完全一致。建树函数本身几乎就是先序遍历的“翻版”区别只是遇到.时不再创建节点而已。2.2 索引参数为什么必须用引用写建树函数时最容易出错的是字符串索引的传递。我用的是这样的签名Node* build(const string s, int idx)注意这里idx必须是引用或者声明成全局变量。如果用普通值传递每个递归层都拿到同一个idx遇到.返回后外层索引没有变化会导致反复读取同一个字符最终陷入死递归程序栈溢出报错。我见过很多初学者的代码是这样写的Node* build(string s, int idx) // 错误示范idx按值传这样建树时左子树递归确实会返回但是回到本层后idx仍然是原来的值再建右子树时可能又从头开始读整个树形就全乱了。记住一句话递归过程中需要“消费”输入序列消费进度必须共享。引用和全局变量都能做到我更推荐用引用函数接口清晰不会和主函数的其他全局状态冲突。2.3 中序和后序遍历还是那套递归模板建树之后遍历就是纯粹的递归输出。中序是左、根、右后序是左、右、根。代码模板固定唯一要留意的是递归终止条件——节点为空就返回不要访问空指针的左右孩子。这两个函数我建议直接背下来因为信息学奥赛里大量题目都用到遍历框架。很多同学会混淆中序和后序其实只要抓住“根的位置”就行中序的根在中间后序的根在最后。写代码时先想清楚当前节点什么时候输出再决定递归调用的顺序。3. 完整代码实现从建树到遍历一次过3.1 结构体定义与函数划分用C手写二叉树可以定义一个结构体struct Node { char data; Node *left, *right; Node(char c) : data(c), left(nullptr), right(nullptr) {} };构造函数里把左右指针初始化为空这是一个很好的习惯。很多运行时错误就是因为新建节点后左右指针没有初始化就访问了导致野指针崩溃。代码最好拆成四个函数build根据扩展先序字符串建树。inorder中序遍历。postorder后序遍历。可选destroy释放整棵树的内存。竞赛里不释放内存也不会被判错但如果你在本地反复测试多组数据建议写一个释放函数避免内存占用越来越高。3.2 建树函数逐行解读把建树函数单独拿出来看Node* build(const string s, int idx) { if (idx s.size()) return nullptr; char ch s[idx]; if (ch .) return nullptr; Node* root new Node(ch); root-left build(s, idx); root-right build(s, idx); return root; }第一行判断idx s.size()是防御性写法。正常情况下输入序列结束时正好所有子树都返回空不会越界但加上这个判断能避免一些边界样例导致崩溃。第二行char ch s[idx];要特别注意这里先取字符然后索引加一。如果写成s[idx]等价于先用后加是对的。但有人喜欢写成char ch s[idx]; idx;效果一样两种写法都可以。切记不要写char ch s[idx];那是先加再用会跳过一个字符。当ch .时返回空指针这个分支是整棵树递归的“刹车”。没有这个分支递归会一直读下去直到越界。如果当前字符是正常字母就创建根节点接着递归建左子树、右子树。这里有一个很关键的点build(s, idx)调用左子树时会从左子树的开头一直处理到左子树的结束位置等左子树调用返回idx已经停在右子树序列的起点。所以紧接着调右子树就好不需要手动计算右子树从哪里开始。这正是前面坚持用引用的原因。3.3 遍历输出细节中序和后序函数不需要返回值直接输出字符即可void inorder(Node* root) { if (root nullptr) return; inorder(root-left); cout root-data; inorder(root-right); } void postorder(Node* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-data; }注意输出不要加空格。有些题要求每个字符占一行有些要求连续字符串一定要看题目的输出格式要求。一本通1304的要求是直接输出两行一行中序一行后序所以这里用cout root-data不换行最后在函数外面统一cout endl。3.4 完整可直接运行的C代码下面给出一个能直接跑通样例的完整程序。我是按多组输入直到EOF写的赛场上很常见。#include iostream #include string using namespace std; struct Node { char data; Node *left, *right; Node(char c) : data(c), left(nullptr), right(nullptr) {} }; Node* build(const string s, int idx) { if (idx (int)s.size()) return nullptr; char ch s[idx]; if (ch .) return nullptr; Node* root new Node(ch); root-left build(s, idx); root-right build(s, idx); return root; } void inorder(Node* root) { if (root nullptr) return; inorder(root-left); cout root-data; inorder(root-right); } void postorder(Node* root) { if (root nullptr) return; postorder(root-left); postorder(root-right); cout root-data; } void destroy(Node* root) { if (root nullptr) return; destroy(root-left); destroy(root-right); delete root; } int main() { string s; while (cin s) { int idx 0; Node* root build(s, idx); inorder(root); cout endl; postorder(root); cout endl; destroy(root); } return 0; }我用输入ABD..EH...CF..G..测试输出DBHEAFCG DHEBFGCA和题目样例吻合。如果题目只给单组输入把while (cin s)改成cin s就行。4. 写二叉树程序为什么总是报运行时错误避坑与调试实录4.1 最常见的五个坑与对应解法很多人在信息学奥赛OJ上提交这题编译通过但一运行就Segmentation Fault。我归纳了五个高频原因。第一递归时索引没有正确更新。前面说过使用按值传递的索引或者忘记idx都会导致递归无限循环或重复读字符。解决办法是使用引用或全局索引并且在读字符后立即自增。第二访问空指针的左右孩子。inorder和postorder函数开头如果没有判断root nullptr当遍历到空节点时会尝试访问root-left直接崩溃。这是二叉树题目的头号杀手递归函数一进来第一件事就应该判空。第三用了char数组但字符串长度不确定越界读入。如果你用scanf(%s, str)不会读入空格但如果题目的空节点用空格表示就会出问题。解决方法是使用string配合cin避免长度问题。第四树退化成链导致递归栈溢出。如果输入序列构造出的树深度特别大递归层数可能超过系统栈大小。信息学奥赛题目一般不会给极端链状数据但如果你在本BT构造深度为10万的树测试就需要改写成非递归。不过1304这题默认不会这么刁钻。第五多组输入时忘记重置索引或释放内存。idx在每次新序列建树前必须重新赋值为0否则上一组数据的位置会带到下一组。释放内存可以避免累计内存增长尤其是循环测试大量数据时。4.2 我常用的调试三板斧遇到建树问题我习惯在纸上模拟一遍递归过程或者在代码中临时打印日志。具体方法是在build函数中加一条调试输出打印当前读取到的字符和索引位置。cout 读到 ch 当前idx idx endl;通过日志可以看到递归是否按预期顺序读入字符。如果是A、B、D、.、.、E……说明正常如果出现反复读A那就说明索引没更新。第二板斧是在遍历函数里打印“进入节点”的信息确认树的形状是否和预期一致。比如在建树完成后临时写一个先序遍历输出看看是否等于原输入序列。如果建出的树先序遍历结果和输入字符串一致说明建树成功。第三板斧是在本地IDE里一步一步调试在build函数调用root-left build(s, idx);这行打上断点查看idx的变化。特别是第一次写递归的同学建议用调试器跟一遍ABD..这个过程递归就不再神秘。4.3 常见问题速查表现象可能原因解决方案程序运行后直接崩溃访问了空指针的成员递归函数开头判空输出结果缺失或乱序递归索引没有正确共享使用引用或全局变量重复建出一样的子树字符自增位置写错检查idx的位置处理多组数据时结果串串每组开始时没有重置索引循环内将idx0输入含空格导致读取失败使用了cin或scanf(%s)改用getline或换掉空格标记极端数据栈溢出递归深度过大改非递归建树/遍历这张表不仅适用于1304在后面做其他二叉树题目时也能套用。只要遇到“二叉树程序报运行时错误”先按这几项排查至少能解决九成问题。5. 从一道题到一类题扩展二叉树的变式与延伸5.1 顺手求深度、节点数、叶子数扩展先序序列建好的树可以当普通二叉树用因此各种统计问题都能接上。比如求二叉树深度代码很简单int depth(Node* root) { if (root nullptr) return 0; return max(depth(root-left), depth(root-right)) 1; }求节点总数就是左右子树节点数之和加1求叶子数就是左右子树都为空时返回1。这些变式在信息学奥赛的树形DP入门中很常见。理解递归时可以把“整棵树的深度”拆成“左子树深度”和“右子树深度”的较大值再加根节点这一层。5.2 层次遍历怎么做扩展先序建树只能得到先序序列但树的层次结构也隐含在里面。层次遍历需要配合队列void levelOrder(Node* root) { if (root nullptr) return; queueNode* q; q.push(root); while (!q.empty()) { Node* cur q.front(); q.pop(); cout cur-data; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }层序遍历是BFS的经典应用很多题目会要求输出每层节点或者判断是否是完全二叉树。有了建好的树这些操作都只是模板套用。5.3 用数组模拟指针避开new的开销在个别内存紧张或追求速度的题目里动态new节点不是最优选择。可以用静态数组模拟二叉树const int MAXN 10005; char val[MAXN]; int lch[MAXN], rch[MAXN]; int cnt 0; int build(const string s, int idx) { if (idx s.size()) return 0; char ch s[idx]; if (ch .) return 0; int cur cnt; val[cur] ch; lch[cur] build(s, idx); rch[cur] build(s, idx); return cur; }这里用0表示空节点用数组下标作为指针。优点是没有动态内存分配不会泄漏调试时还能直接看数组内容。信息学奥赛中有很多题目用这种静态写法更稳妥尤其是一次建多棵树或者树节点很多时。5.4 与其他建树方式对比扩展先序是“唯一单序列建树”的特例。除此之外常见的建树组合还有先序中序、后序中序。为什么中序必须配合另一个序列因为中序只能确定左右孩子的相对顺序但无法确定根是谁先序或后序能确定根但无法划分左右子树。两者结合才能还原二叉树。对比一下思路先序中序先序第一个字符是根在中序里找到根的位置左边是左子树中序右边是右子树中序再根据长度在先序中切出左右子树的先序。后序中序后序最后一个字符是根其余思路相同。扩展先序空节点已经帮我们划好了左右子树的边界递归时不需要再查中序只用消费一个序列。理解这三种方式可以帮你把树结构的递归逻辑串起来。扩展二叉树是其中最直观、最容易上手的一个。最后再分享一点个人体会我做这题时最大的收获不是背会了建树代码而是彻底理解了“递归消费输入”这件事。很多同学写二叉树程序总觉得递归很玄其实只要抓住两个东西终止条件和子问题拆分。扩展二叉树恰好把这两点展现得非常清楚——遇到空节点终止一个完整节点加左右子树递归就是子问题拆分。如果你正在刷《信息学奥赛一本通》建议不要直接抄代码先自己在纸上把ABD..EH...CF..G..这个序列的建树过程走一遍再动手写。写错几次也没关系用调试器跟一遍比看十遍题解都管用。这道题的价值绝不仅仅是一道水题它后面的递归思想会一直跟着你走到树形DP、线段树、平衡树早一天想通后面就轻松一天。
