Which of the follwing sequence

[单选题]

下面序列哪个不可能是二叉搜索时的后序遍历结果？

```
1,2,3,4,5
```
```
3,5,1,4,2
```
```
1,2,5,4,3
```
```
5,4,3,2,1
```

查看答案及解析

指尖凉hsz

B：后序遍历，既然2是最后一个遍历到的，则说明2是根结点，则2的左孩子只能是1，因为只有1小于2，后序遍历的结果肯定是1先遍历到，然后去遍历2的有孩子，最后遍历2，最后的结果只能是1，？，？，？，2。

发表于 2017-09-14 16:59:18 回复(0)

xd321

首先我们观察题目：二叉搜索树，后序遍历两个知识点。

二叉搜索树，用于搜索，因此 内部节点没有重复的元素 。另外， 满足二叉树的性质，左子树都比自己小，右子树都比自己大。 那么可想而知，如果按照后序遍历，先左后右最后自己的顺序来遍历树，数组的最后一个元素肯定是自己（父节点），然后剩余的部分分成两个部分，第一部分都比自己小（左子树部分），第二部分都比自己大（右子树部分），因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。

发表于 2016-06-30 11:04:18 回复(4)

小杨vita

二叉查找树后续遍历的最后一个结点，必能把前面的部分分成两部分，左边比它小，右边比它大

发表于 2015-09-19 22:03:11 回复(5)

大海真大

问题意思是不可能是二叉搜索树的后续遍历的是：

二叉搜索树是排序过的二叉树，即左子树中的结点值小于根结点的值，右子树中的结点值大于根节点的值

直观起见，如下图所示（A,C,D都不唯一，此图仅提供了一种答案）

编辑于 2016-04-06 14:23:10 回复(4)

DFS

后序遍历，最后一个肯定是根节点，然后把前面的分成 < 或 > 的，有一点，就是按着给的顺序如3 5，小的一定在大的数左边，大的在右边或者上边， B不对，，，，

发表于 2018-03-03 11:34:50 回复(0)

黏黏糖

题目中问的是：不是二叉搜索树后序遍历的序列。

由于二叉搜索树满足：左孩子 < 根节点 < 右孩子

因此若后序遍历二叉搜索树，首先，最后一个结点肯定是根节点。根节点将序列分为两部分，前一部分比根节点小，后一部分比根节点大。或者都比根节点小（大），此种情况为无右（左）子树。

发表于 2017-05-25 19:10:18 回复(1)

MnM~

二插搜索树，所以，每个树的左子树都小于右子树。后序遍历，从左子树到右子树，然后根节点。所以从最后一个元素向前看，连续的大于根节点的，就为右子树，连续的小于的就是左子树。所以，我们从后向前看，对数据进行划分左右子树，得出结果。例如12345 那么，根节点为5，1234所有都为左子树。然后，4为根节点，123为左子树，一步步构造出树。对于B:35142 2为根节点，那么3为左，514为右，然而1小于2所以，错误。 C:12543 3为根，12为左，54为3 然后2为根1为左！4为根5为右

发表于 2022-04-06 11:17:46 回复(0)