剑指Offer题解 - Day46

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

力扣题目链接[1]

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

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

     5
    / \
   2   6
  / \
 1   3

「示例 1：」

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

「提示：」

1. 数组长度 <= 1000

思路：

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

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

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

• 后序遍历的顺序是左右根，那么我们需要将数组分为左子树、右子树和根节点。
• 根节点就是当前的右边界。从左边界开始遍历，寻找第一个大于根节点的节点值，将该节点记做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);
};

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

分析：

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

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

总结

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

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

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vwxx5/