题解 | #二叉搜索树的后序遍历序列#

思路：（seq=[4,8,6,12,16,14,10]）
seq[-1]为二叉搜索树的root。根据root可以将seq分为left=[4,8,6]和right=[12,16,14]两部分，对right中的元素进行遍历，如果存在小于root的元素，说明不能组成二叉搜索树。
否则，再对left和right分别进行判断，方法同上。
递归退出的条件：len(se)=1
代码：
class Solution:

def VerifySquenceOfBST(self, sequence):
    # write code here
    if len(sequence)==0:
        return False
    if len(sequence)==1:
        return True
    root=sequence[-1]
    left=[]
    right=[]
    for i in range(len(sequence)-1):
        if sequence[i]<root:
            left.append(sequence[i])
        else:
            break
    right=sequence[len(left):len(sequence)-1]

    for j in range(len(right)):
        if right[j]<root:
            return False

    l= True
    r=True
    if len(left)>0:
        l=self.VerifySquenceOfBST(left)
    if len(right)>0:
        r=self.VerifySquenceOfBST(right)
    return l and r