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

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