剑指offer33.二叉搜索树的后序遍历序列

**剑指Offer33: 二叉搜索树的后序遍历序列**

二叉搜索树（Binary Search Tree）是计算机科学中一个非常重要的数据结构，它能够有效地组织和检索大量数据。二叉搜索树的定义是：对于任意结点，左子树中的值都小于该结点的值，而右子树中的值都大于该结点的值。

后序遍历（Postorder Traversal）是二叉树的一种遍历方式，它首先访问左子树，然后访问右子树最后访问根结点。后序遍历可以用来求出二叉树中结点的值的平均值、最大值和最小值等。

在本题中，我们需要判断一个给定的后序遍历序列是否是某个二叉搜索树的后序遍历序列。如果是，则返回 true；否则，返回 false。

**示例**

输入：[4,8,6,12,10,16,14]
输出：true输入：[1,2,3,4,5,6,7]
输出：false**解决方案**

我们可以使用后序遍历的性质来解决这个问题。具体来说，我们可以先找到最右边的结点（即最后一个访问的结点），然后检查它是否满足二叉搜索树的定义。如果不满足，则直接返回 false。

class Solution:
 def verifyPostorder(self, postorder: list[int]) -> bool:
 # 如果序列长度为0 或1，直接返回 true if len(postorder) <=1:
 return True # 找到最右边的结点（即最后一个访问的结点）
 root = postorder[-1]
 # 初始化左子树和右子树的索引 i =0 while i < len(postorder) -1 and postorder[i] < root:
 i +=1 # 检查左子树是否满足二叉搜索树的定义 for j in range(i, len(postorder) -1):
 if postorder[j] >= root:
 return False # 检查右子树是否满足二叉搜索树的定义 for j in range(i, len(postorder) -1):
 if postorder[j] < root:
 return False # 如果所有结点都满足二叉搜索树的定义，则返回 true return True

solution = Solution()

print(solution.verifyPostorder([4,8,6,12,10,16,14])) # Output: Trueprint(solution.verifyPostorder([1,2,3,4,5,6,7])) # Output: False