输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 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$。