剑指 是否为二叉搜索树
二叉搜索树的后序遍历序列
http://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd
使用递归方法,先找到大于根节点的节点,该节点为左右子树分界点,然后分别去判断左右子树是否为二叉搜索树。注意数组为空时,不是二叉搜索树。
# -*- coding:utf-8 -*- class Solution: def JudgeSquence(self,sequence): if len(sequence)<=1: return True root =sequence[-1] for i in range(len(sequence)): if sequence[i]>root: break # if sequence[i]==root: # return True for j in range(i,len(sequence)-1): if sequence[j]<root: print(sequence[j]) return False if i==0: return self.VerifySquenceOfBST(sequence[i:-1]) if i==len(sequence)-1: return self.VerifySquenceOfBST(sequence[:i]) return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:-1]) def VerifySquenceOfBST(self, sequence): # write code here if len(sequence)==0: return False return self.JudgeSquence(sequence)