欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指—JZ23二叉搜索树的后序遍历序列(递归)

程序员文章站 2022-03-23 09:12:41
题目描述输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。解题思路二叉搜索树有一个很好的特性,就是左子树的节点值均小于根节点值,右子树的节点值均大于根节点值,对于一个树,后序遍历就是左右根,这个左的序列元素均<根,右的序列元素均>根,因此就可以进行判断,从左往右找出第一个大于根节点的值,然后再从这个点开始遍历到数组倒数第二个元素(因为最后一个元素为根节点),如果一旦出现比根节点小的就直接返回Fal...

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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

相关标签: 算法