CSP-J 入门级 · CSP 2019 入门级第一轮 第 14 题

假设一棵二叉树的后序遍历序列为 $\texttt{DGJHEBIFCA}$，中序遍历序列为 $\texttt{DBGEHJACIF}$，则其前序遍历序列为（）。

拿到题先找后序最后一个字母A，它就是整棵树的根；接着去中序里看A把树切成哪两段，左段就是左子树节点，右段是右子树节点，再分别在后序里截取对应长度的片段，递归重复这步就能把树搭出来，前序则是按'根左右'输出。

最容易栽跟头的地方就是左右子树切分后，在后序里截取长度时数错了，或者把后序里'根'的位置搞混，导致左子树后序序列里偷偷混进了右子树的根节点。还有，有些同学看到后序是'左右根'，就下意识以为前序也是'左右根'，结果把左右子树顺序写反了。另外，递归到底层时，如果左子树只有一个节点，千万别把它当成空树处理，否则前序序列里会少一个字母，选项里那些把字母顺序搞乱的（比如把F和I位置互换）往往就是这种低级失误造成的。

考点与概念：本题考的是二叉树遍历序列的还原。核心概念很简单：后序遍历是'左子树→右子树→根'，中序遍历是'左子树→根→右子树'。已知中序和后序就能唯一确定一棵二叉树，因为中序告诉我们根在哪里，后序告诉我们谁是根。前序遍历则是'根→左子树→右子树'，一旦树搭好了，前序自然就顺出来了。

命题人怎么挖坑：这类题通常不会让你画树，而是直接给两个序列让你选前序。命题人喜欢在左右子树长度相等、或者某个子树只有一个节点的地方埋雷，比如这道题左子树有6个节点、右子树只有3个，数字不对称，学生很容易在后序截取时数错个数，把右子树的根节点'偷'进左子树的后序里。还有，选项里经常把左右子树的顺序颠倒，或者把某个子树里的节点顺序打乱（比如把F和I换位置），这些都是典型的陷阱。

思考心法：拿到题先别急着套公式，按这个顺序走： 1. 看后序最后一个字母，这就是当前树的根（这题是A）。 2. 在中序里找到这个根，它左边全是左子树节点，右边全是右子树节点（这题A左边是DBGEHJ，右边是CIF）。 3. 数一下左子树有几个节点（6个），就回到后序序列，从开头数6个字母，这就是左子树的后序（DGJHEB）；剩下的（IFC）就是右子树的后序。 4. 对左子树和右子树重复步骤1-3，直到所有子树都处理完。 5. 最后按'根→左→右'的顺序把结果拼起来，就是前序。

一步步还原：

• 整棵树根是A。中序里A左边有6个节点（D、B、G、E、H、J），所以左子树后序取前6个：DGJHEB；右边3个节点（C、I、F），后序取后3个：IFC。
• 看左子树DGJHEB：根是B。在中序DBGEHJ里，B左边只有D（1个节点），所以左子树左子树后序是D；B右边是GEHJ（4个节点），后序是GJHE。
• 继续拆GEHJ：根是E。中序里E左边是G（1个），右边是HJ（2个）。再拆HJ：根是H，左边J（1个），右边空。
• 拆右子树IFC：根是C。中序CIF里C左边是I（1个），右边是F（1个）。再拆I和F，都是单节点树。
• 把所有节点按'根左右'顺序排出来：A→B→D→E→G→H→J→C→I→F，即ABDEGHJCFI。

验证与避坑：选项B就是这个序列，完全匹配。其他选项要么把F和I位置弄反（D），要么把G和J顺序搞错（C），要么把左右子树整体颠倒（A）。做题时千万别在数节点个数时粗心，尤其是左右子树长度不相等的时候，一定要在中序里数清楚再回头去后序截取。

考频与趋势：二叉树遍历是高频考点，题库共201题，GESP六级就占了100题，说明基础级别考得最多。近年爆发式增长：2023年19题、2024年58题、2025年67题，尤其是2025年几乎占了全部，可见命题人正把二叉树作为重点，难度也在悄悄提升。入门级每年只有1-3题，但2025年CSP入门级考了3题，说明连入门级也开始重视这个知识点。

预测：既然2025年201题里二叉树占了67题，且GESP六级仍是最大头，未来几年（2026-2027）这个考点大概率会继续霸榜，尤其是GESP六级和七级。入门级虽然题量少，但2025年已经考了3题，可以预见2026年可能也会保持2-3题的规模，但不会像提高级那样爆发。所以，别觉得入门级简单就放松，二叉树还原题在入门级也会以单选题形式出现，而且可能会更侧重细节（比如节点个数判断），这正是命题人挖坑的高发区。