# 剑指Offer题解 - Day46

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

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

参考以下这颗二叉搜索树：

1
2
3
4
5

示例 1：

输入:[1,3,2,6,5]
输出:true

1
2

提示：

数组长度 <= 1000

思路：

首先题目有两个先决条件，那就是：

该二叉树是二叉搜索树
数组的数字都互不相同

基于此，可以总结出以下规律：

后序遍历的顺序是左右根，那么我们需要将数组分为左子树、右子树和根节点。
根节点就是当前的右边界。从左边界开始遍历，寻找第一个大于根节点的节点值，将该节点记做m 。也就意味着从左边界到m节点的上一个节点为止，都是左子树。m节点到右边界减一的节点为止，都是右子树。右边界本身就是根节点。
其中需要判断左子树的值是否都小于根节点，右子树的值是否都大于根节点。在寻找第一个大于根节点的时候，其实已经验证了左节点的值都是小于根节点的。因此只需要验证右子树。维护一个节点p，遍历右子树的每个节点，直到遇到小于等于根节点的值为止。
最终满足二叉搜索树的条件就是节点p与右边界相等，以及递归左子树和递归右子树都满足二叉搜索树。

根据以上分析，我们可以写出如下代码：

# 递归

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
const recur = (postorder, left, right) => {
    if (left >= right) return true;
    let p = 0; // 初始化指针
    while(postorder[p] < postorder[right]) p++; // 寻找右子树的第一个节点
    let m = p; // 右子树的第一个节点
    while(postorder[p] > postorder[right]) p++; // 判断右子树的节点是否都大于根节点
    return p === right && recur(postorder, left, m - 1) && recur(postorder, m, right - 1);
}

var verifyPostorder = function(postorder) {
    return recur(postorder, 0, postorder.length - 1);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度 O(n^2)。
空间复杂度 O(n)。

分析：

解题的核心思路就是将数组分为 [左子树|右子树|根节点] ，同时需要判断左子树是否都小于根节点，右子树是否都大于根节点。都满足条件后，然后递归左子树和右子树。

复杂度方面，在最坏情况下，二叉搜索树退化为链表时，每次寻找只能找到一个根节点，因此时间复杂度是O(n^2) ，而函数调用栈需要占用O(n) 的空间。

# 总结

本题使用递归进行判断是否为二叉搜索树。最核心的两个判断条件是：

left >= right，如果条件成立，意味着子树的元素小于等于1，则不需要进行判断，直接返回true。
p === right ，如果条件成立，意味着右子树的所有节点的值都大于根节点。

剑指Offer题解 - Day45 剑指Offer题解 - Day47