单选题

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA, 中序遍历序列为 DBGEHJACIF, 则其前序遍历序列为(     )。

【正确答案】 B
【答案解析】

根据中序、 后序遍历的特点, 可以确定 A 是根结点(在后序遍历的最后一个), 再根据中序遍历的特点, 可以知道 DBGEHJ 为左子树, CIF 为右子树。
再看右子树的后序遍历为 IFC, 可以确定 C 为右子树的根结点; 再加上中序为 CIF, 说明 C 无左子树, 只有右子树。
而左子树的后序遍历为 DGJHEB, 因此 B 为左子树的根结点, 再结合中序遍历, 可以得知 B 的左子树只有D, GEHJ 都是右子树。
GEHJ 子树的后序遍历是 GJHE, 说明 E 是根, HJ 为 E 的右子树, G 是 E 的左子树。 最后可以得出, H 为HJ 子树的根, J 为右子树。
然后再由前序遍历, 可以得到: ABDEGHJCFI。