24，二叉搜索树的后序遍历序列

由后序遍历可知，序列的最后一个数字是树的根节点的值。数组中前面的数字，可以分为两部分：第一部分是左子树节点的值，他们都比根节点的值小；第二部分是右子树节点的值，他们都比根节点的值大。

我们可以先确定左子树的前半部分，再确定右子树的部分，再传入到递归函数中即可。

需要注意的地方：

一、递归函数时，传入到递归函数的子列表一定不能弄错！

可以写几个具体的例子，然后确定传入的子列表的表示方式。

二、递归结束条件？

若是传入的sequence为None，那么就一定返回False。
但是，如果是递归到底，叶子结点为None的情况就不能返回False,应该返回True了，这应该怎么办呢？

这时候，可以在把子列表传入递归函数以前，先对子列表的长度进行判断，如果长度小于等于0 ，那么就不调用递归函数即可。

那么也应该返回一个True，作为递归函数返回的值。因此，可以事先把left（或者right）设置为True，然后再在递归时，对这两个变量进行赋值。

代码实现:

class Solution:
    #若是输入为空，那么怎么分辨
    def VerifySquenceOfBST(self,sequence):
        # write code here
        if len(sequence) == 0:
            return False

        index = 0
        length = len(sequence)
        # 判断左子树的位置，[0:index]
        for i in sequence[0:length]:
            if i < sequence[-1]:
                index += 1
            else:
                break
        # 判断右子树是否都大于根节点
        for i in sequence[index:length-1]:
            if i > sequence[-1]:
                pass
            else:
                return False
        
        # 先设置left为True
        left = True
        #若是子列表不为空，就再对left进行赋值，最终返回left
        if len(sequence[0:index]) > 0:
            left = self.VerifySquenceOfBST(sequence[0:index])
        right = True
        if len(sequence[index:length-1]) > 0:
            right = self.VerifySquenceOfBST(sequence[index:length-1])
        return left & right