剑指Offer_编程题23：二叉搜索树的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

牛客网：链接

二叉搜索树节点的值的大小，是根据中序遍历的先后顺序赋值的。中序遍历为“左中右”，在二叉搜索树中表现为：左节点的值 < 根节点的值 < 右节点的值。 

根据后序遍历的性质，尾元素必定是树的根，同时小于尾元素的值是左子树，大于尾元素的值为右子树，且序列前半部分均小于尾元素，后半部分均大于尾元素（如果同时存在左右子树的话），可以将序列划分左子树序列和右子树序列，然后递归比较每一段是否满足此性质。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if sequence == []:
            return False

        root = sequence[-1]
        length = len(sequence)
        index = 0
        # 二叉搜索树的左子树结点小于根节点
        '''
        下面这个for循环特别需要主要index=i必须写在if语句外面,
        否则就会发生当root结点前的所有元素小于root的时候, 正确判断应该为True,
        但是因为if语句没有进入, index = 0 ,
        在进入二叉搜索树的右子树结点大于根结点的for循环的时候, 因为sequence的数都小于root, 就会判断出错
        '''
        for i in range(length-1):
            index = i
            if sequence[i] > root:
                break

        # 二叉搜索树的右子树结点大于根结点
        # 这个循环中范围起始点必须是index+1, 不能为index
        # 因为当root结点前的所有元素小于root的时候,index=length-2,
        # 此时sequence[index]<root, 但是按照range(index, length-1), 第一个元素sequence[j]==sequence[index] < root, 返回False, 实际应该返回True才对
        # 而使用index+1, 因为已经默认index>root, 所以从后面一个开始盘算右子树结点是否大于root, 也不会影响结果
        for j in range(index+1, length-1):
            if sequence[j] < root:
                return False

        left = True
        if index > 0:
            left = self.VerifySquenceOfBST(sequence[:index])

        right = True
        if index < length-1:
            right = self.VerifySquenceOfBST(sequence[index:length-1])
        return left and right