刷过《信息学奥赛一本通》的同学，对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的左子树读D，D的左右都是.，于是D的两个子树返回空，D子树结束。
• 继续建B的右子树，读E，E的左子树读H，H的两个儿子都是空，然后读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 常见问题速查表

这张表不仅适用于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; queue<Node*> 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、线段树、平衡树，早一天想通，后面就轻松一天。