剑指offer33.二叉搜索树的后续遍历序列

判断一个数组是不是二叉搜索树的后序遍历结果

思路：二叉搜索树的后序遍历序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，他们都比根节点的值小；第二部分是右子树节点的值，他们都比根节点的值大。用同样的方法确定与数组每一部分对应的子树的结构

class Solution:
    def verifySequenceOfBST(self, sequence):
        """
        :type sequence: List[int]
        :rtype: bool
        """
        if len(sequence) == 0:
            return True
        root = sequence[-1]
        for index,element in enumerate(sequence):
            i = index
            if element>root:
                break
        for element in sequence[i:]:
            if element<root:
                return False
        left =True
        if i>0:
            left = self.verifySequenceOfBST(sequence[:i])
        right=True
        if i<len(sequence)-1:
            right = self.verifySequenceOfBST(sequence[i:-1])
        return left and right