【剑指offer】二叉搜索树的后序遍历序列（python）

思路类似于“树的子结构”
1.二叉搜索树的性质
若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

2. 根据序列的最后一位确认出根节点，因为二叉树左子树都小于根节点，右子树都大于根节点，所以由根节点确定左子树最后一位，从而得到右子树开始的点，验证右子树是否都大于根节点，递归验证左右两子树。

class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        return self.Define(sequence, 0, len(sequence)-1)
    def Define(self,sequence,first,last):
        if first + 1 >= last:
            return True
        root = sequence[last]
        pre = first
        # 根据根节点的值确定左子树最后一个结点位置
        while sequence[pre] <= root and pre < last:
            pre += 1
        # 右子树
        for i in range(pre, last):
            if sequence[i] < root:
                return False
        return self.Define(sequence, first, pre - 1) and self.Define(sequence,pre, last- 1)