一道有意思的填空题

happy_idea

选择题：给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（）

A. EDBFGCA    B. EDBGCFA    C. DEBGFCA    D. DBEGFCA

这是CSP的真题，但是同学们的答案都很不一致。

大家来研究研究，讨论讨论。

BZR

我发表一下我的观点：

题目告诉我们：

1. 前序：ABDECFG

2. 中序：DEBACFG

根据前序应先访问根，所以根是 A。

而中序中 A 的位置是：DEB | A | CFG，所以左子树：DEB；右子树：CFG。

而左子树前序是 BDE，中序是 DEB，所以根是 B。

中序中 B 的位置是：DE | B | 空，左子树：DE，右子树：空。

左子树前序是 DE，中序是 ED，根就是 D。

中序中 D 的位置是：空 | D | E，左子树：空，右子树：E。

所以左子树是：

     B

   /

D

  \

   E

再分析右子树前序是 CFG，中序则是 CFG，所以根是 C。

中序中 C 的位置是：空 | C | FG，左子树：空，右子树：FG。

右子树前序：FG，中序：FG，所以根是 F。

中序中 F 的位置：空 | F | G，左子树：空，右子树：G

所以右子树是：

C

\

  F

    \

     G

合并，整棵树便是：

          A

       /    \

     B      C

   /            \

D             F

   \               \

    E             G

根据题目要求，要后序遍历一下：

左子树：E, D, B

右子树：G, F, C

根：A

→ E, D, B, G, F, C, A → EDBGFCA，但因为选项中并没有这一选项，所以我也不清楚...