剑指—JZ23二叉搜索树的后序遍历序列(递归)
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路
二叉搜索树有一个很好的特性,就是左子树的节点值均小于根节点值,右子树的节点值均大于根节点值,对于一个树,后序遍历就是左右根,这个左的序列元素均<根,右的序列元素均>根,因此就可以进行判断,从左往右找出第一个大于根节点的值,然后再从这个点开始遍历到数组倒数第二个元素(因为最后一个元素为根节点),如果一旦出现比根节点小的就直接返回False,举个例子:
1, 4, 6, 3, 7, 9, 5
这里5是根节点,从头开始遍历,当遍历到6的时候终止(因为6已经大于5了)。然后从6开始遍历,当遍历到3时发现比根节点还要小,意味着右子树中存在比根节点还小的元素,程序直接返回False。如果一次遍历没问题,就对左右子树进行遍历
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
root = sequence[-1]
i = 0
while i < len(sequence) - 1:
if sequence[i] > root:
break
i += 1
for j in range(i, len(sequence) - 1):
if sequence[j] < root:
return False
left = True; right = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[:i])
if i < len(sequence) - 1:
right = self.VerifySquenceOfBST(sequence[i: len(sequence) - 1])
return left and right
本文地址:https://blog.csdn.net/jianghuia/article/details/107878098