Python 代码
class Solution:
def verifySequenceOfBST(self, seq):
if not seq:
return True
i = 0
while seq[i] < seq[-1]:
i += 1
for j in seq[i:-1]:
if j < seq[-1]:
return False
return self.verifySequenceOfBST(seq[:i]) and self.verifySequenceOfBST(seq[i:-1])
一开始为空应该返回True
def verifySequenceOfBST(self, seq): def dfs(seq): if not seq: return True i = 0 root = seq[-1] while seq[i] < root: i += 1 for j in seq[i:-1]: if j < root: return False return dfs(seq[:i]) and dfs(seq[i:-1]) if not seq: return False return dfs(seq)写得很清晰
python的切片还是好用啊