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

题目

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

选项

• A. $\texttt{ABCDEFGHIJ}$
• B. $\texttt{ABDEGHJCFI}$
• C. $\texttt{ABDEGJHCFI}$
• D. $\texttt{ABDEGHJFIC}$

答案

B

题解

答案是 B．$\texttt{ABDEGHJCFI}$。

关键是记住三种遍历的顺序：

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

因此，后序的最后一个字母是根，再用这个根把中序分成左右两部分，不断重复即可。

① 后序 DGJHEBIFCA 的最后一个字母是 A，所以根是 A。中序按 A 划分：

``text DBGEHJ | A | CIF 左子树 右子树 ``

左子树有 6 个节点，右子树有 3 个节点，因此后序对应划分为：

``text DGJHEB | IFC | A 左子树 右子树 根 ``

② 对左右子树重复这个过程：

• 左子树的根是 B，中序为 D | B | GEHJ。
• B 的左孩子是 D。
• 右子树的后序是 GJHE，根是 E；中序为 G | E | HJ。
• 所以 E 左边是 G，右边以 H 为根，H 的右孩子是 J。
• 右子树的根是 C，中序为 C | IF。
• C 没有左子树，右子树的后序是 IF，所以根是 F，F 的左孩子是 I。

得到二叉树：

``text A / \ B C / \ \ D E F / \ / G H I \ J ``

按“根 → 左 → 右”读出前序遍历：

$$ \boxed{\texttt{ABDEGHJCFI}} $$