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

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param sequence int整型一维数组 
# @return bool布尔型

# 左子树<根节点 与 右子树>根节点选取一个用来返回False就够了
# 因为在寻找右子树的时候已经用到前面这个条件了
#
class Solution:
    def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
        # write code here
        if len(sequence) == 0:
            return False
        index = 0
        for i in range(len(sequence)): # 注意这里的终止值不能为len(sequence)-1，要考虑数组长度为1的情况
            if sequence[i] > sequence[-1]:
                index = i
                break
        for j in range(i, len(sequence)-1):
            if sequence[j] < sequence[-1]:
                return False
        for k in range(0, index):  # 遍历左子树，若左子树中有节点大于根节点则返回假
            if sequence[k] > sequence[-1]:
                return False
        left = True
        right = True
        if len(sequence[:index]) > 0:
            left = self.VerifySquenceOfBST(sequence[:index])
        if len(sequence[index:len(sequence)-1]) > 0:
            right = self.VerifySquenceOfBST(sequence[index:len(sequence)-1])
        return left and right