题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路:后序遍历:左右根,其特点是list的最后一个元素是二叉树的根节点。所以加上二叉搜索树的特点,我们可以得出,找到根节点root后,前面小于root的都为其左子树,大于root的都是其右子树,然后递归调用即可。
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
if len(sequence) <= 0:
return False
#获得树的根节点root
root = sequence[-1]
#二叉搜索树中左子树的值小于跟节点,找到第一个大于root的i
for i in range(len(sequence)):
if sequence[i]>root:
break
#节点i之后的(包括节点i)应该是大于root的右子树的节点,若出现小于root,则返回false
for j in range(i,len(sequence)):
if sequence[j]<root:
return False
#递归调用判断其左右子树是不是满足要求。
left = True
right = True
if i>0:
left = self.VerifySquenceOfBST(sequence[:i])
if len(sequence)-i>1:
right = self.VerifySquenceOfBST(sequence[i:-1])
return left and right