# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not len(sequence):
return False
if len(sequence) == 1:
return True
# 定义整个数的长度
length = len(sequence)
# 根节点的值
root = sequence[-1]
i = 0
# 判断左子树的位置
while sequence[i] < root:
i = i 1
k = i
# 判断右子树的值是否都大于根节点root
for j in range(i,length-1):
if sequence[j] < root:
return False
left_s = sequence[:k]
right_s = sequence[k:length-1]
left , right = True, True
# 递归遍历左右子树的值
if len(left_s) > 0:
left = self.VerifySquenceOfBST(left_s)
if len(right_s) > 0:
right = self.VerifySquenceOfBST(right_s)
return left and right