已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DB

[单选题]

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为多少？

```
DGEBFHAC
```
```
DGEBHFCA
```
```
DEGHBFCA
```
```
DEGBHACF
```

推荐

河湖之恋

答案选B。

前序遍历确定根节点，中序遍历确定左右子树。

A，（BDEG，CFH）

（B，（D，EG））；（C，（，FH））

（E，（G ，））；（F，（H，））

编辑于 2015-02-03 11:29:52 回复(1)

牛客472844号

发表于 2015-08-16 17:24:39 回复(0)

bjty

记住口诀：

前序遍历：根左右

中序遍历：左根右

后序：左右根

发表于 2015-12-24 16:20:12 回复(0)

繁星的夜空2012

已知二叉树的中序遍历和前序遍历，如何求后序遍历

第一步，root最简单，前序遍历的第一节点就是root。

第二步，对于前序遍历，除了A是root外，剩下的结点都是root的左右子树。没有其它信息

第三步，观察中序遍历，其中root结A左侧的DBGE必然是root的左子树，A右侧的CHF必然是root的右子树。

第四步，观察左子树dgb，左子树的中的根节点必然是大树root的leftchild。一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。而从 前序遍历可知，根节点后面的第一个结点就是左子树的根节点

第五步，root的右子树的结点 CHF 也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。

如何知道哪里是前序遍历中的左子树和右子树的分界线呢？通过中序遍历去数节点的个数。

在上一次中序遍历中，root左侧是 DBGE ，所以有4个节点位于root左侧。那么在前序遍历中，必然是第1个是A，第2到第5个由BDEG过程，第6个就是root的右子树的根节点了，是C。

第六步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。

第七步，其实，如果仅仅要求写后续遍历，甚至不要专门占用空间保存还原后的树。只需要稍微改动第六步，就能实现要求。仅需要把第六步的递归的过程改动为如下:

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

发表于 2016-12-22 11:06:05 回复(0)

付出

前序遍历特点：访问根节点-》前序访问左树-》前序访问右树---确定根节点为A
中序遍历特点：中序遍历左树-》访问根节点-》中序访问右树---确定A的左边都是左树，右边都是右树，根据前序访问规则和中序访问规则可以知道B是左树的根节点，根据前序遍历“ABDEGCFH”知道C是右树根节点，左树右树节点的排列顺序可以根据前序中序的遍历特点得出，结果如下

B E C

D G F H

发表于 2015-11-26 17:39:35 回复(0)