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

• 对于后续遍历序列，序列的最后一个值一定是树的根结点，而由二叉搜索树的性质：左小右大，我们可以从头开始遍历，当遍历到某个值比根结点大时停止，记为flag，此时flag之前的所有数值都是二叉搜索树的左子树的结点，flag以及flag之后的所有数都是二叉搜索树的右子树的结点。
  这是由二叉搜索树以及后序遍历共同决定的。
  接下来，我们就可以把任务交给递归，同样的方法去判断左子树和右子树是否是二叉搜索树，

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        if len(sequence) <= 2:
            return True
        for i in range(len(sequence)):
            if sequence[i] > sequence[-1]:
                break
            if i == len(sequence) - 1:
                return True
        for j in range(i, len(sequence)):
            if sequence[j] < sequence[-1]:
                return False
        left = True
        if i > 1:
            left = self.VerifySquenceOfBST(sequence[:i]) 
#注意这里切到i就可，因为前面的数都比i这个数小，没必要取，如果取可能会让前面是错误的数字判断为TRUE
        right = True
        if j < len(sequence):
            right = self.VerifySquenceOfBST(sequence[i:len(sequence)-1]) 
#注意这里初始值也切到i,不然可能会导致队列中没有数字，直接返回FALSE，
# 因为初始值切了fla***，如果末位置取到最后一个值也没意义，因为最初值永远比末位值大（之前已经判断过），可能导致后面判断出现错误，所以不取列表最后的值
        return left and right
        # write code here