当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EG

[单选题]

当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是

```
BDEAGFHC
```
```
EBDGACFH
```
```
HGFEDCBA
```
```
HFGDEABC
```

推荐

速效扎心丸

正确答案选B

由前序序列可知根节点为H

然后由中序序列可知根节点的左子树有EGBD，右子树有FAC

再根据前序序列看，左子树为GEDB，那么左子树的根节点为G

继续看中序序列，以G为根节点的左子树就为E，右子树为BD

以此类推，画出树如下：

后序遍历为EBDGACFH

编辑于 2015-02-06 11:06:18 回复(0)

王浩

前序遍历是HGEDBFCA那么根节点是H所以后序遍历的最后一个节点应该是H排除法选B

发表于 2015-06-07 10:41:25 回复(0)

InGodWeTrust

选B：

由前序遍历可知其根节点为H,因此直接选B

发表于 2017-04-07 10:34:22 回复(0)

纯牛奶YYDS

前序序列：根结点-左结点-右结点

中序序列：左结点-根结点-右结点

后序序列：左结点-右结点-根结点

前序序列：HGEDBFCA

中序序列：EGBDHFAC

后序序列：EBDGACFH

方法：根据前中序列，一层一层剥离提取

前序序列可知：H是根结点

在中序序列中： EGBD 是左子树 FAC是右子树

在前序序列中：第二层左子树 GEDB中，G为根结点 ; 第二层右子树 FCA中， F 为根结点

在中序序列中： EGBD中， G为根结点，第三层 E为左结点，BD为右子树; FAC中， F为根结点，第三层 AC为右子树

在前序序列中：DB为第三层左子树，D为根结点 ; CA为第三层右子树，C为根节点

在中序序列中： BD中 B为第四层左结点; AC中，A为第四层左结点