Question

已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是

已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是
A)acbed B)decab C)deabc D)cedba
谁能帮我画个图，我看了网上的对遍历的介绍，还是有点乱

Answer 1

选D

首先看后续遍历，最后的c是二叉树的根节点，然后看中序遍历，最后一个又是c，所以这个二叉树根节点没有右子树。

c的位置得到后，再看后续遍历，e在c前面，所以e是c的左孩子节点，e的位置得到。

然后再看中序遍历，e前面只有一个d，所以d是e的左孩子节点，d的位置得到；剩下的b和a就在e的右子树。

然后再看后序遍历，dabec，d是一个叶子节点，那么就还有一个叶子节点，那么这个节点就一定是a，那么b就是e的右孩子节点，最后再结合中序遍历就可得出所表示得二叉树。（如果这步没看懂，可以在前面得基础上一个一个的试，也不麻烦，就四种可能，最后只有一个是符合的）

Answer 2

中序遍历:DEBAC    

后序遍历:DABEC

推导如下：

1、从后序可知树根为C,因为最后的节点是树根。

2、从中序的规则可知树根在中间,树根的左边是左孩子,右边是右孩子。很明显树根C是没有右孩子,只有左孩子DEBA。

中序遍历:DEBA

后序遍历:DABE

推出E是左子树的根结点,并且存在左子树D,右子树BA,因为从中序遍历可知E的左边是D,右边是BA

中序遍历:BA

后序遍历:AB

推出B是右子树的根结点,并且存在右子树,但没有左子树,因为从中序遍历可知B只有右子树,没有左子树。

还原二叉树如下图：

前序为：CEDBA

推导的方法只需记住下面的规则即可，然后逐步分割法,就像我上面那样推导。拿到左右子树反复套用下面的遍历规则,很快就可以还原一棵完整的树。

1.先序遍历：根、左、右

2.中序遍历：左、根、右

3.后序遍历: 左、右、根

Answer 3

这种题，主要考虑个节点的逻辑关系，先序遍历就是：根左右后序遍历就是：左右根，中序遍历就是：左根右。
抓住一个关键，例如本题中后序和中序第一个节点都是D，那么可以确定：D没有右子树，D本身是一个节点的左子树。中序遍历，D后面是E，说明D父节点是E，在草稿上画出来这个关系。在看中序遍历E后面是B，说明B是E的右子树，这样我们确定了3个节点了。再看中序的遍历B后的是A，但我们无法确定是左还是右，先放着，继续看后序遍历E后面是C，通过这个条件，说明C可能是E的父节点的右子树，也可能就是E的父节点，但是本题一共只有5个节点，所以C肯定是E的父节点。这样，我们可以确定4个节点了，这剩下A节点。要区分A是左还是右，我们看后序遍历，A是在D之后，B之前，这个条件也只能说A是B子节点，但仍然不能说明左右。所以我觉得：这道题有2个解：A在左在右，都是正确的。A是左是右，都符合后序和中序的遍历，都为正确。所以，只画这个图是不完整的，应该把A分别为左右节点的图都画出来，作为答案，A的位置不同，虽然先序遍历的结果都一样，但是图是不一样的。
不知你看懂没有。

Answer 4

前序: 根左右
中序: 左根右
后序: 左右根

```````````````````C
/
e
/ \
d b
\
a

前序: cedba

追问

总体的大概清楚了，但前序，中序或者后续都要过左叶，对于过左叶的顺序有没有什么规定？比如这道题中序和后序都先经过左叶，但顺序却不同，一个deba，一个dabe

Answer 5

dbacde，就是这样的，虽然我不会，但是瞎写谁不会啊，😂😂