CSP-J 2023 第一轮 第 11 题：由前序中序求后序遍历

题目

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?

选项

• A. EDBGFCA
• B. EDGBFCA
• C. DEBGFCA
• D. DBEGFCA

答案

A

题解

正确答案是 A. EDBGFCA。

记住三种遍历顺序：

• 前序：根 → 左 → 右
• 中序：左 → 根 → 右
• 后序：左 → 右 → 根

前序 ABDECFG 的第一个节点是 A，所以根节点是 A。在中序中按 A 分开：

``text DEB | A | CFG 左子树 右子树 ``

接着分别分析：

• 左子树：前序是 BDE，中序是 DEB。根为 B，D、E 都在它的左子树中；其中 D 为根，E 是 D 的右孩子。因此后序为 EDB。
• 右子树：前序和中序都是 CFG。根为 C，右孩子为 F，F 的右孩子为 G。因此后序为 GFC。

最后按“左 → 右 → 根”拼接：

``text EDB + GFC + A = EDBGFCA ``