一、题目：二叉搜索树的后序遍历序列

题目描述

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

思路：

　　二叉搜索树：根节点 > 左子树 and  根节点 < 右子树

　　后序遍历：左、右、根

　　后序遍历的二叉搜索树【左（小）、右（大）、根节点】

　　找到右节点所在位置 mid ，然后递归判断 【左】是不是二叉搜索树、【右】是不是二叉搜索树

　　代码：

　　

def VerifySquenceOfBST(self, sequence):        # write code here        if not sequence:            return False        def helper(sequence):            if len(sequence) <= 2:                return True            head = sequence[-1]            mid = 0            for i,s in enumerate(sequence):                if s > head:                    mid = i                    break                elif i == len(sequence) - 1 and s == head:                    mid = i            for i in range(mid):                if sequence[i] > head:                    return False            for i in range(mid,len(sequence)):                if sequence[i] < head:                    return False            return helper(sequence[:mid]) and helper(sequence[mid:len(sequence)-1])        return helper(sequence)