本文主要是介绍剑指Offer 刷题记录 python 33-，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

33. 二叉搜索树的后序遍历序列

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) <= 2:
            return True

        root = postorder[-1]
        i = len(postorder)-2
        while postorder[i] > root and i>=0: 
            i = i-1
        if i == -1:
            res = self.verifyPostorder(postorder[0:-1])
        else:
            for j in range(i,-1,-1):
                if(postorder[j] > root):
                    return False
            res = self.verifyPostorder(postorder[i+1:-1]) and self.verifyPostorder(postorder[0:i+1])
        return res

•  递归
• 是二叉搜索树的判断依据：list长度小于等于2 or list的最后一个值一定可以将list从中划分，前半部分小于最后一个值，后半部分大于最后一个值 or list的最后一个值是整个list中最小/大的
• 循环递减公式一定是 for j in range(i,-1,-1)，循环递减至索引0

这篇关于剑指Offer 刷题记录 python 33-的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！