输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
解题思路：
后序遍历的定义：【左子树 | 右子树 | 根节点】
二叉搜索树定义：左子树中所有节点值 $<$ 根节点的值；右子树中所有节点的值 $>$ 根节点的值；其左右子树也为二叉搜索树。
根据以上两个定义，可以得到如下结论：
- 拿到序列最后一个元素的值 $x$ ，可以将序列分为左子树和右子树。其中，小于 x 的连续元素的集合为左子树的序列；大于 x 的连续元素的结合为右子树的序列。
- 左子树的序列和右子树的序列同样满足结论 $1$。
根据以上的结论，可以使用一个指针 $p$ 和 $m$。$p$ 指向的元素会与 $x$ 进行对比，$m$ 记录的是左子树的右边界（不包含 $m$）。
验证函数
**参数传递：**后序遍历数组 $postorder$，数组的左右边界（包含）$l$、$r$。
终止条件： $l$ 大于等于 r 时，返回 $true$。
递推工作：
- $p$ 指针指向 $l$，$x$ 为 $postorder[r]$ 的值
- 循环检查：如果 $p$ 指向的元素小于 $x$，说明该元素属于左子树，$p$ 自增。
- 用 $m$ 记录 $p$ 的值，此时 $[l, m-1]$ 区间为左子树。
- 循环检查：如果 $p$ 指向的元素大于 $x$，说明该元素属于右子树，$p$ 自增。
- 通过以上两个循环，对于合法的序列，此时应该有 $p = r$，然后分别对左子树区间 $[l, m-1]$ 和右子树区间 $[m, r-1]$ 进行下一层的递归，返回递归结果。
代码：
public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length == 0) {
return true;
}
return verifyPostOrder(postorder, 0, postorder.length - 1);
}
private boolean verifyPostOrder(int[] postOrder, int l, int r) {
if (l >= r) {
return true;
}
int p = l;
while (postOrder[p] < postOrder[r]) {
p++;
}
// [l,m) 为左子树
int m = p;
while (postOrder[p] > postOrder[r]) {
p++;
}
// 如果是合法的后序遍历，那么此时 p == r
return p == r && verifyPostOrder(postOrder, l, m - 1) && verifyPostOrder(postOrder, m, r - 1);
}
复杂度分析
-
时间复杂度$O(N^2)$：$N$ 为序列的长度。验证函数每一层只会去掉一个根节点，因此递归占用 $O(N)$。最坏情况下，树退化成链表，每一层占用的时间为 $O(N)$ 。
-
空间复杂度$O(N)$：$N$ 为序列的长度。最差情况下，树退化成链表，递归深度达到 $N$。