题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
# write code here
if not sequence: return False
if len(sequence) == 1: return True
root = sequence[-1]
idex = -1
for i in range(len(sequence)):
if sequence[i]<root and idex!=-1:
return False
if sequence[i]>root and idex==-1:
idex = i
if idex == 0 or idex == -1:
return self.VerifySquenceOfBST(sequence[0:len(sequence)-1])
return self.VerifySquenceOfBST(sequence[0:idex]) and self.VerifySquenceOfBST(sequence[idex:len(sequence)-1])