输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解法一:递归法
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self,sequence):
# write code here
if len(sequence)==0:
return False
index = 0
for i in range(len(sequence)):
if sequence[i]>sequence[-1]:
index = i
break
for j in range(i,len(sequence)):
if sequence[j]0:
left = self.VerifySquenceOfBST(sequence[:index])
if len(sequence[index:-1])>0:
right = self.VerifySquenceOfBST(sequence[index:-1])
return left and right
作者:数挖小飞飞