剑指offer：二叉搜索树的后序遍历序列-创新互联

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

成都创新互联公司专业为企业提供泾源网站建设、泾源做网站、泾源网站设计、泾源网站制作等企业网站建设、网页设计与制作、泾源企业网站模板建站服务，10年泾源做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

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

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文名称：剑指offer：二叉搜索树的后序遍历序列-创新互联
文章分享：http://scjbc.cn/article/dspphe.html