题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。