题解 | #二叉搜索树的后序遍历序列#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param sequence int整型一维数组
# @return bool布尔型
#
class Solution:
    def VerifySquenceOfBST(self, sequence: list[int]) -> bool:
        # write code here
        if not sequence:
            return False

        def Verify(sequence):
            if len(sequence) == 1 or len(sequence) == 0:
                return True
			#每次取序列的最后一个数作为根节点
            root = sequence[-1]
			#将序列更新，去掉根，只剩左右子树的节点
            sequence = sequence[:-1]
            index = 0
            for i in sequence:
                if i > root:
				  #如果i的值大于root了，将cii的值对应的索引作为分割，左边子树和右边子树的分界线进行分割
                    index = sequence.index(i)
                    break
				#当比较到最后一个也没有确定i的值，此时，说明序列的值全部小于根，没有右子树，将index置为序列的长度+1，这样在划分左右字数的时候可以将左字树划分进去全部
                elif sequence.index(i) ==len(sequence)-1:
                    index= sequence.index(i)+1
                else:
                    pass

            for j in sequence[index:]:
                if j < root:
                    return False
				 #划分左右字数，如果Index比序列值小或者相等
            if index <= len(sequence):
                left = sequence[:index]
                right = sequence[index:]
            else:
			  #index比序列值大，没有右子树
                left =sequence[:index]
                right=[]
            return Verify(left) and Verify(right)

        return Verify(sequence)