GESP 八级 · GESP202609 C++ 八级 第 4 题

某二叉树的先序遍历序列为 A B D E C F G ，中序遍历序列为 D B E A F C G ，则其后序遍历序列为 （　　）。

先序定根，中序分左右。根节点 A 在中序中位置将树分为左子树（D B E）和右子树（F C G）。递归处理左右子树：左子树根为 B，其左为 D、右为 E；右子树根为 C，其左为 F、右为 G。后序遍历遵循"左→右→根"顺序，依次输出各子树后序结果。

选项 B 错在遗漏左子树根节点 B 的位置；选项 C 错在将右子树根节点 C 误植为 G；选项 D 错在右子树后序顺序颠倒（应为 F G C 而非 F C G）。

考纲定位 本题考查《GESP 考试大纲》八级"数据结构与算法"模块中的二叉树遍历与递归构造。命题人特意选用先序 + 中序组合，卡住的是考生对"先序定根、中序分左右"这一核心规律的掌握——许多考生看到先序序列就机械地按顺序输出，完全忽略中序序列对左右子树的划分作用。

解题思维 先序序列首元素 A 必为根节点。在中序序列中找到 A 的位置，其左侧 D B E 构成左子树，右侧 F C G 构成右子树。递归处理左子树：先序 B D E 中 B 为根，中序 D B E 中 D 在 B 左侧、E 在 B 右侧，故左子树为 D、右子树为 E。递归处理右子树：先序 C F G 中 C 为根，中序 F C G 中 F 在 C 左侧、G 在 C 右侧，故左子树为 F、右子树为 G。后序遍历遵循"左→右→根"顺序，依次输出各子树后序结果：左子树后序为 D E B，右子树后序为 F G C，根为 A，合并得 D E B F G C A。

陷阱拆解 选项 B 错在遗漏左子树根节点 B 的位置；选项 C 错在将右子树根节点 C 误植为 G；选项 D 错在右子树后序顺序颠倒（应为 F G C 而非 F C G）。

反命题思维 若将中序序列改为 D B E A G C F，则右子树结构变为 G 为根、C 为左、F 为右，后序结果将变为 D E B G C F A，选项 A 不再成立。若将先序序列改为 A B D E C G F，则右子树根仍为 C，但左右子树互换，后序结果变为 D E B G F C A，选项 C 成立。