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

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

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

解题思路：

后序遍历的定义：【左子树 | 右子树 | 根节点】

二叉搜索树定义：左子树中所有节点值 $<$ 根节点的值；右子树中所有节点的值 $>$ 根节点的值；其左右子树也为二叉搜索树。

根据以上两个定义，可以得到如下结论：

1. 拿到序列最后一个元素的值 $x$ ，可以将序列分为左子树和右子树。其中，小于 x 的连续元素的集合为左子树的序列；大于 x 的连续元素的结合为右子树的序列。
2. 左子树的序列和右子树的序列同样满足结论 $1$。

根据以上的结论，可以使用一个指针 $p$ 和 $m$。$p$ 指向的元素会与 $x$ 进行对比，$m$ 记录的是左子树的右边界（不包含 $m$）。

验证函数

**参数传递：**后序遍历数组 $postorder$，数组的左右边界（包含）$l$、$r$。

终止条件： $l$ 大于等于 r 时，返回 $true$。

递推工作：

1. $p$ 指针指向 $l$，$x$ 为 $postorder[r]$ 的值
2. 循环检查：如果 $p$ 指向的元素小于 $x$，说明该元素属于左子树，$p$ 自增。
3. 用 $m$ 记录 $p$ 的值，此时 $[l, m-1]$ 区间为左子树。
4. 循环检查：如果 $p$ 指向的元素大于 $x$，说明该元素属于右子树，$p$ 自增。
5. 通过以上两个循环，对于合法的序列，此时应该有 $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$。

大佬解法