输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
Solutions
规律转化成代码的能力还值得练练啊……注意这里注释掉的做法是不合适的,因为有可能第一个 for 循环都不执行!!!!这样的话 split_i 就还是0,此时不应该0,而是遍历到最后了!
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence is None or len(sequence)<=0:
return False
root = sequence[-1]
split_i = 0
# for i in range(len(sequence)-1):
# if sequence[i] > root:
# print 'up', i
# split_i = i
# break
# print 'split_i', split_i, 'sequence size', len(sequence)
# for i in range(split_i, len(sequence)-1):
# if sequence[i] < root:
# print 'below', i
# return False
for node in sequence[:-1]:
if node > root:
break
split_i += 1
for node in sequence[split_i:-1]:
if node < root:
return False
left = True
if split_i > 0:
left = self.VerifySquenceOfBST(sequence[:split_i])
right = True
if split_i < len(sequence)-1:
right = self.VerifySquenceOfBST(sequence[split_i:len(sequence)-1])
return left and right