CSP-J 2024 第一轮 第 12 题：已知二叉树的前序遍历为[A,B,D,E,C,F,G],中...

题目

已知二叉树的前序遍历为 $[A, B, D, E, C, F, G]$，中序遍历为 $[D, B, E, A, F, C, G]$，请问该二叉树的后序遍历结果是？（  ）

选项

• A. $[D, E, B, F, G, C, A]$
• B. $[D, E, B, F, G, A, C]$
• C. $[D, B, E, F, G, C, A]$
• D. $[D, B, E, F, G, A, C]$

答案

A

题解

答案是 A：$[D,E,B,F,G,C,A]$。

记住三种遍历顺序：

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

前序的第一个元素是 $A$，所以 $A$ 是根节点。在中序遍历中，以 $A$ 为界： $$ [D,B,E]\quad A\quad [F,C,G] $$ 因此，左子树包含 $D,B,E$，右子树包含 $F,C,G$。

再看前序中对应的两段：

• 左子树前序为 $[B,D,E]$，根是 $B$；结合中序 $[D,B,E]$，可知 $D$ 是左孩子，$E$ 是右孩子。
• 右子树前序为 $[C,F,G]$，根是 $C$；结合中序 $[F,C,G]$，可知 $F$ 是左孩子，$G$ 是右孩子。

得到二叉树：

``text A / \ B C / \ / \ D E F G ``

按后序“左 → 右 → 根”遍历，依次得到： $$ \underbrace{D,E,B}_{左子树},\quad \underbrace{F,G,C}_{右子树},\quad \underbrace{A}_{根} $$

所以选 A。