题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param sequence int整型一维数组
# @return bool布尔型
# 左子树<根节点 与 右子树>根节点选取一个用来返回False就够了
# 因为在寻找右子树的时候已经用到前面这个条件了
#
class Solution:
def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
# write code here
if len(sequence) == 0:
return False
index = 0
for i in range(len(sequence)): # 注意这里的终止值不能为len(sequence)-1,要考虑数组长度为1的情况
if sequence[i] > sequence[-1]:
index = i
break
for j in range(i, len(sequence)-1):
if sequence[j] < sequence[-1]:
return False
for k in range(0, index): # 遍历左子树,若左子树中有节点大于根节点则返回假
if sequence[k] > sequence[-1]:
return False
left = True
right = True
if len(sequence[:index]) > 0:
left = self.VerifySquenceOfBST(sequence[:index])
if len(sequence[index:len(sequence)-1]) > 0:
right = self.VerifySquenceOfBST(sequence[index:len(sequence)-1])
return left and right