难度: Medium
请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。
示例 1：
输入: postorder = [4,9,6,5,8] 输出: false 解释：从上图可以看出这不是一颗二叉搜索树
示例 2：
输入: postorder = [4,6,5,9,8] 输出: true 解释：可构建的二叉搜索树如上图
提示：
数组长度 <= 1000postorder中无重复数字
Submission
运行时间: 40 ms
内存: 14.8 MB
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(i, j):
if i >= j:
return True
m = i
while postorder[m] < postorder[j]:
m += 1
n = m
while postorder[m] > postorder[j]:
m += 1
return m == j and recur(i, n-1) and recur(n, j-1)
return recur(0, len(postorder)-1)
Explain
此题解采用递归分治的方法。首先，后序遍历的最后一个元素为二叉搜索树的根节点。对于任意子数组，都可以利用最后一个元素（根节点）将数组分成两部分：左子树部分（所有小于根节点的元素）和右子树部分（所有大于根节点的元素）。算法从初始的根节点开始，逐步向下验证每个子树是否也满足二叉搜索树的后序遍历的特点。递归函数 'recur(i, j)' 负责检验子数组 postorder[i:j+1] 是否可以代表一个二叉搜索树的后序遍历。如果数组可以正确地按照上述方式分割，并且左右子树也都是有效的二叉搜索树的后序遍历，则整个数组是有效的。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(i, j):
# 递归终止条件，当子数组长度为0或1时，直接返回True
if i >= j:
return True
# 寻找左子树与右子树的分界点
m = i
while postorder[m] < postorder[j]:
m += 1
n = m
# 确认右子树中的所有元素都大于根节点
while postorder[m] > postorder[j]:
m += 1
# 确保整个数组都被正确检查过，并且左右子树也都是合法的后序遍历
return m == j and recur(i, n-1) and recur(n, j-1)
return recur(0, len(postorder)-1)
Explore
在递归函数中，左子树和右子树的分界点是通过比较数组元素与根节点的大小来确定的。后序遍历中，数组的最后一个元素是根节点，我们从数组的第一个元素开始，寻找第一个大于根节点的元素。所有在这个元素之前的都属于左子树（即都小于根节点），而这个元素及之后的，直到根节点前的元素，则应属于右子树（即都大于根节点）。这样可以将数组分为两部分，左子部分和右子部分，分别对应二叉搜索树的左子树和右子树。
递归终止条件设置为子数组长度为0或1时返回True，这是因为一个空的数组或者仅包含一个元素的数组自然符合二叉搜索树的后序遍历序列的条件。空数组没有元素，不违反规则；单个元素的数组也不会违反二叉搜索树的左小右大原则。因此，这样的设置简化了递归过程，并且能够有效地处理边界条件，使得算法更加简洁和高效。
在二叉搜索树中，根据其定义，任何节点的右子树中的所有节点都必须大于该节点。因此，在验证后序遍历序列时，必须确保位于分界点右侧（即右子树部分）的所有元素都大于根节点。这样的检查是为了保证遵循二叉搜索树的基本规则，即左小右大。如果右子树中存在小于或等于根节点的元素，则序列不能代表一个合法的二叉搜索树的后序遍历。
虽然在逻辑上看似可以合并这两个循环，因为第一个循环用于找到左子树和右子树的分界点，第二个循环用于确认右子树中所有元素都大于根节点，但实际上合并这两个循环可能会复杂化代码逻辑。第一个循环结束的位置即是右子树的开始，如果在第一个循环内同时检查右子树的所有元素，可能会导致代码难以理解和维护。不过，从性能优化的角度考虑，可以在一个循环内完成所有检查，只要确保代码的可读性和维护性不受影响。