BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 4 题

已知 $7$ 个结点的二叉树的先根遍历是 $1\ 2\ 4\ 5\ 6\ 3\ 7$（数字为结点编号），中根遍历是 $4\ 2\ 6\ 5\ 1\ 7\ 3$，则该二叉树的后根遍历是（ ）。

这题考二叉树遍历唯一确定树结构。拿到题先别急着背顺序，盯着中序序列找根节点，它在先序里的位置就是左右子树的边界，顺着这个逻辑把树画出来，后序自然就出来了。

最容易栽跟头的就是死记硬背遍历口诀，一看到数字就条件反射选个看着顺眼的，完全没看树长什么样；或者把左右子树分错，导致后序里根节点的位置放错，比如把根节点提前到子树后面去了；还有人会纠结叶子结点计算，但这题其实不需要数叶子，只要树画对了，后序序列是唯一的，根本不存在算错的可能。

这道题考查的是二叉树遍历序列与树结构之间的唯一对应关系，以及后序遍历的定义。命题人喜欢用这种‘给前序和中序求后序’的题型，因为学生往往背了‘前序根左右、中序左根右、后序左右根’的口诀，却忘了怎么从序列还原树。考频方面，二叉树遍历在 CSP-J/S 及 GESP 中属于高频考点，近五年在单选和填空里反复出现，尤其是结合完全二叉树性质或层序遍历的题目，学生失分率较高。趋势上，单纯背顺序的题越来越少，现在更爱考‘根据前序+中序画树’或‘根据层序+中序画树’，甚至结合完全二叉树存储结构（数组下标关系）来挖坑，要求学生真正理解遍历的递归本质。预测未来，这类题会继续以还原树结构为核心，可能增加层序遍历的干扰项，或者把后序序列打乱一部分让你补全，难度会维持在中等偏上。解题心法：拿到题先别想答案，盯着中序序列，根节点一定在中序里唯一出现，它在先序序列的首位，所以先序的第一个数就是整棵树的根。然后看这个根在中序里的位置，左边全是左子树的节点，右边全是右子树的节点。再回到先序序列，根后面紧跟着的是左子树的根，再往后是右子树的根，这样就能把左右子树的范围切分出来。这个过程其实就是递归：对每一个子树重复‘找根、分界、递归左右’的操作，直到子树只有一个节点或为空。画图是必须的，哪怕只是简单的树形草图，也能避免左右子树搞混。避坑指南：千万不要用叶子结点公式（n/2 或 (n+1)/2）来硬套，这题只给了遍历序列，树的结构已经唯一确定，叶子数只是顺便算出来的，跟后序序列无关；也别把后序遍历顺序记成‘根左右’或‘左根右’，后序永远是‘左右根’，根节点永远在最后。正确做法是：先序第一个是 1，所以 1 是根；中序里 1 左边是 4,2,6,5，右边是 7,3，说明左子树节点是{4,2,6,5}，右子树节点是{7,3}。回到先序，1 后面是 2，2 是左子树的根；中序里 2 左边是 4，右边是 6,5，所以 2 的左孩子是 4，右子树节点是{6,5}。继续递归：左子树 4 在中序里是单点，所以 4 是叶子；右子树{6,5}在先序里是 5，所以 5 是根，中序里 5 左边是 6，右边空，所以 5 的左孩子是 6，6 是叶子。右子树{7,3}在先序里是 3，所以 3 是根，中序里 3 左边空，右边是 7，所以 3 的右孩子是 7，7 是叶子。整棵树画出来就是：根 1，左孩子 2，2 的左孩子 4，2 的右孩子 5，5 的左孩子 6，1 的右孩子 3，3 的右孩子 7。后序遍历就是按‘左子树后序、右子树后序、根’的顺序输出：左子树{4,2,5,6}的后序是 4,6,5,2；右子树{7,3}的后序是 7,3；最后根 1。拼起来就是 4,6,5,2,7,3,1，对应选项 A。