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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param sequence int整型一维数组 
# @return bool布尔型
#
class Solution:
    def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
        # write code here
        # 先判空
        if not sequence:
            return False
        # 找出后序遍历的根节点
        len_list = len(sequence)
        root = sequence[len_list-1]
        index = 0
        # 找出左右子树的右子树分界节点
        for i in range(len_list):
            # 注意边界条件，是大于等于 都可以是右子树
            if sequence[i]>=root:
                index = i
                break
        # 判读分界点右边是否满足二叉搜索树的条件，即右子树全大于等于根节点
        # 注意这里不能
        for i in range(index, len_list):
            if sequence[i]<root:
                return False
        
        # 使用一个flag判断左右子树是否满足，分割的只去除根节点，index要包含进去
        # 注意index是不是首个或者倒数第二个元素，如果是则不要分割
        f_left = True
        if index>0:
            # 要记得在if中更新标志的状态
            f_left = self.VerifySquenceOfBST(sequence[:index])
        f_right =True
        if index < len_list-1:
            f_right = self.VerifySquenceOfBST(sequence[index:-1])
        return f_left and f_right

根节点就是数组的最后一位，所以

• 第一步：找到数组最后一位，即根节点root。紧接着
• 第二步：获取整个数组的长度，开始遍历并与root值比较，第一个大于root的值就是左右子树的分界点。
• 第三步：遍历右子树，验证是否符合二叉搜索树的概念；如上图，以12为分界点的右边所有节点都是大于root的，所以是符合二叉搜索树的。
• 第四步：继续往下递归，查看余下的左右子树是否符合。