剑指offer：二叉搜索树的后序遍历序列

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

成都创新互联公司专注于企业成都全网营销、网站重做改版、来凤网站定制设计、自适应品牌网站建设、H5网站设计、商城网站制作、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为来凤等各大城市提供网站开发制作服务。

class Solution:
    """
    一个二叉搜索树BST满足： max(左子树) < 根节点 < min(右子树)
    由于题目给出的是一个后序遍历，那么序列的最后一个元素就应该是根节点。
    因此我们从BST的定义出发，遍历整个序列，找到第一个大于根节点的元素k，k以前的元素属于左子树，
    从k开始到根节点之前的元素属于右子树。
    如果遍历整个序列之后得到的左右子树都满足BST的定义，则递归判断左子树和右子树是否满足BST定义
    """
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False

        root = sequence[-1]  # 获取根节点
        """
        查找第一个大于根节点的元素，得到左右子树的分界点
        """
        idx = 0
        while idx < len(sequence) - 1:
            if sequence[idx] > root:
                break
            idx += 1

        # 需要验证右子树是否满足BST，即所有右子树的节点都大于根节点，
        # 如果不满足则这个序列不是BST的后序遍历
        for i in range(idx, len(sequence) - 1):
            if sequence[i] < root:
                return False

        # 如果这个序列是BST的后序遍历，那么递归判断左右子树是否分别满足BST
        left = True
        if idx > 0:
            left = self.VerifySquenceOfBST(sequence[: idx])

        right = True
        if idx < len(sequence) - 1:
            right = self.VerifySquenceOfBST(sequence[idx: -1])

        return left and right

标题名称：剑指offer：二叉搜索树的后序遍历序列
网站URL：http://cdiso.cn/article/gesiph.html