面试题33：二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

知识点

二叉搜索树

Qiang的思路

想要做这道题，首先需要知道什么是二叉搜索树。

二叉搜索树就是左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。这样在搜索时可以二分查找。

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

所以，我们只需要根据序列的最后一个元素将除了最后一个元素的整个序列划分为两部分，小于的部分和大于的部分，如果划分失败这说明这个序列并不是一个二叉搜索树的后序遍历序列。然后在对第一部分和第二部分通过同样的方法去处理。最终就能判断是不是一个二叉搜索树的后续遍历序列了。

# -*- 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。
个人网站：https://www.myqiang.top。