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

题目描述

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

思路

首先明确二叉搜索树的概念。
二叉搜索树，左子树的均小于根，右子树均大于根。
任意的左右子树也是二叉搜索树。
其次，后续遍历的顺序为 左，右，根。
根据后续遍历的顺序，先找到根节点。再根据二叉搜索树的特点，找到左右子树。分别检查左右子树的值是否正确（与根节点相比）。
递归的对左右子树进行同样的判断。

代码

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        root = sequence[-1] #找到根节点
        #找到比root大的第一个节点，以此划分左右子树
        i = 0
        for node in sequence[:-1]:
            if sequence[i] > root:
                break
            i += 1
        #这一步保证右子树是规范的(全部比根节点大)
        for node in sequence[i:]:
            if node < root:
                return False
        #递归对左子树判断
        left = True
        if len(sequence[:i]) >0:
            left = self.VerifySquenceOfBST(sequence[:i])
        #递归对右子树判断
        right = True
        if len(sequence[i:-1])>0:
            right = self.VerifySquenceOfBST(sequence[i+1:])
        return left and right