剑指—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