二叉搜索树的后序遍历序列
2019-03-27 本文已影响0人
momo1023
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
if len(sequence) <= 2:
return True
l = len(sequence)
root = sequence[-1]
# 注意此处应该是range(l),否则会错
for i in range(l):
if sequence[i] > root:
break
for val in sequence[i:-1]:
if val < root:
return False
left = True
right = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[:i])
if i < l - 1:
right = self.VerifySquenceOfBST(sequence[i:-1])
return left and right