注意:对于二叉搜索树, 左子树的值都小于根节点,右子树的值都大于根节点。
后序遍历的根节点是最后一个值,
然后前一部分小于根,是左子树,后一部分大于根,是右子树。
然后再递归的判断左子树和后子树的部分,是否为后序遍历。
代码:
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence == None or len(sequence) <= 0:
return False
root = sequence[-1]
i = 0
while i < len(sequence)-1:
if sequence[i] > root:
break
i += 1
j = i
while j < len(sequence)-1:
if sequence[j] < root:
return False
j += 1
left = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[:i])
right = True
if i < len(sequence)-1 :
right = self.VerifySquenceOfBST(sequence[i:-1])
return left and right