确定该序列是否为二进制排序树的后遍历python

标题: 给定序列，确定它是否是二进制排序树的后遍历结果

分析: 首先，我们必须知道什么是排序的二叉树. 用这种方式定义了二进制排序树. 二进制排序树可以是空树，也可以是具有以下属性的二进制树:

（1）如果左子树不为空，则左子树上所有节点的值小于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；

（3）左右子树也是二进制排序树；

（4）没有节点具有相同的键值

因此，按``左右根''顺序遍历二进制排序树获得的序列具有以下特征: 该序列与中间分开，左序列的值小于最后一个序列的值，以及正确序列的值大于序列的最后一个值. 显然，序列的最后一个值是根节点，此分界点是左右子树的分界点. 因此，我们按顺序遍历序列并找到大于根节点的第一个值，该值区分左子树和右子树. 同时，如果该点左侧的值大于根节点的值，或者该点右侧的值小于根节点的值，则此序列不满足要求. 如果满足要求，则继续按照以上过程判断左右子树，显然这是一个需要递归解决的问题.

判断代码:

class Solution:
    #判断序列是否是二叉排序树的后续遍历序列    
    def VerifySquenceOfBST(self, sequence):
        if len(sequence)==0:
            return False
        if len(sequence)==1:
            return True
        root=sequence[-1]#根节点的值
        border=len(sequence)-1#必须初始化边界点的值，因为有可能没有右子树，就无法按照第一个大于root的方法找到border
        for i in range(len(sequence)-1):
            if sequence[i]>root:
                border=i
                break
        for i in range(len(sequence)-1):#边界点左边的值小于root，右边的值大于root
            if sequence[i]<root and i>border:
                return False
            if sequence[i]>root and i<border:
                return False
        if border==len(sequence)-1 or  border==0:#没有左子树或没有右子树
            return self.VerifySquenceOfBST(sequence[:-1])
        else:
            return (self.VerifySquenceOfBST(sequence[:border]) and self.VerifySquenceOfBST(sequence[border:len(sequence)-1]))

在判断过程中，应该注意的是，根据第一种方法二叉排序树中序遍历二叉排序树中序遍历，找到比根更大的边界是可能的还是不可能的. 此时，右子树不存在，因此必须初始化边框，并且应初始化左子树. 否则，应该专门处理右子树不存在的情况.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-194953-1.html