访谈问题33: 二叉搜索树的后遍历序列

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

二叉搜索树

要执行此问题，您首先需要知道什么是二叉搜索树.

二叉搜索树意味着左子树中的所有节点均小于根节点，而右子树中的所有节点均大于根节点. 这样，您可以在搜索时以二进制搜索.

基于二叉搜索树的概念，很容易认为后顺序由三部分组成. 第一部分是左子树的后序遍历序列，第二部分是右子树的后序遍历序列，第三部分是根的值. 第三部分只是序列的最后一个元素.

因此二叉排序树中序遍历，我们只需要将除最后一个元素以外的整个序列分为两个部分，根据该序列的最后一个元素，该部分小于和大于两个部分. 如果除法失败，则表示该序列不是二叉搜索树. 后顺序遍历序列. 然后以相同的方式处理第一部分和第二部分. 最后二叉排序树中序遍历，可以判断它是否是二叉搜索树的后续遍历序列.

# -*- coding:utf-8 -*-
class Solution:
    def getResult(self, sequence):
        if len(sequence)<=1:
            return True
        m=sequence[-1]
        flag=-1
        for i in range(len(sequence)-1):
            if flag==-1 and sequence[i]>m:
                flag=i
            if flag!=-1 and sequence[i]<m:
                return False
        return self.getResult(sequence[:i]) and self.getResult(sequence[i:-1])
        
    def VerifySquenceOfBST(self, sequence):
        # write code here
        return False if len(sequence)==0 else self.getResult(sequence)

通过测试，发现空序列不是二叉搜索树的后遍历子序列.

原始作者，如果您需要转载和其他问题，请联系: lwqiang_chn@163.com.

个人网站: .

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-183817-1.html