判断一个数组是不是二叉搜索树的后序遍历结果
思路:二叉搜索树的后序遍历序列中,最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分:第一部分是左子树节点的值,他们都比根节点的值小;第二部分是右子树节点的值,他们都比根节点的值大。用同样的方法确定与数组每一部分对应的子树的结构
class Solution:
def verifySequenceOfBST(self, sequence):
"""
:type sequence: List[int]
:rtype: bool
"""
if len(sequence) == 0:
return True
root = sequence[-1]
for index,element in enumerate(sequence):
i = index
if element>root:
break
for element in sequence[i:]:
if element<root:
return False
left =True
if i>0:
left = self.verifySequenceOfBST(sequence[:i])
right=True
if i<len(sequence)-1:
right = self.verifySequenceOfBST(sequence[i:-1])
return left and right