class Solution:
def verifySequenceOfBST(self, sequence):
"""
:type sequence: List[int]
:rtype: bool
"""
self.seq = sequence
return self.dfs(0, len(sequence) - 1)
def dfs(self, start, end):
if start >= end:
return True
#根节点
root = self.seq[end]
#左边 - 找k
k = 0
while k < end and self.seq[k] < root:
k += 1
#右边
for i in range(k + 1, end):
if self.seq[i] < root:
return False
return self.dfs(start, k - 1) and self.dfs(k, end - 1)