若一棵二叉树的前序遍历序列和后序遍历序列分别为1， 2， 3

[单选题]

若一棵二叉树的前序遍历序列和后序遍历序列分别为1， 2， 3， 4 和 4， 3， 2， 1，则该二叉树的中序遍历序列不会是（）。

```
1， 2， 3， 4
```
```
2， 3， 4， 1
```
```
3， 2， 4， 1
```
```
4， 3， 2， 1
```

查看答案及解析

蔡蔡撸代码ing

4个结点，分别位于4层，1 在第一层，2在第二层，3在第三层，4在第四层，根据左中右，出现在第一个的一定是最左边的结点，而C选项中，3为第一个，所以3在最左边，而3的子节点是4，所以紧接着出现的是4，而答案是2 所以错误。

发表于 2016-12-13 10:29:05 回复(0)

liamzhou

前序序列为NLR，后序序列的逆序为LRN，要使NLR=NRL（后序序列的反序），则L或R为空，这样的二叉树每层就只有一个结点，高度为4。1为根结点，由于根结点只有左孩子或右孩子，因此在中序序列中，1或在序列首或在序列尾，ABCD皆满足。仅考虑以1的孩子结点2为根的子树，同理在中序序列中，2或在序列首或在序列尾，ABD皆满足，C不满足。

发表于 2017-08-21 20:12:08 回复(6)