[LC]33. 二叉搜索树的后序遍历序列

🚩传送门：力扣题目

题目

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

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

     5
   /  \
 2    6

/ \ 1 3

示例 1：

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

示例 2：

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

解题思路：递归

后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。

二叉搜索树定义：

1. 左子树中所有节点的值 < 根节点的值；
2. 右子树中所有节点的值 > 根节点的值；
3. 其左、右子树也分别为二叉搜索树。

算法思想：遍历区间划分左右子树，递归左右子树检查是否为二叉搜索树

1. 划分左右子树

• 后续遍历数组的区间，根结点一定是元素
• 遍历数组的区间区间元素，寻找 第一个大于根节点 的节点，索引记为 此时左子树区间 、右子树区间

1. 判断是否为二叉搜索树

   左子树有上限 ，右子树有下限

• 左子树区间 内的所有节点值都应该在范围 。
• 右子树区间 内的所有节点值都应该在范围 。

复杂度分析

时间复杂度：，最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点

空间复杂度：， 最差情况下（即当树退化为链表），递归深度将达到 。

官方代码

class Solution {
    public static boolean verifyPostorder(int[] postorder) {
        // postorder数组、区间范围[0,postorder.length - 1] 下限、上限
        return verifyPostorder(postorder, 0, postorder.length - 1,Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    private static boolean verifyPostorder(int[] postorder, int start, int end, int lowerlimit,int toplimit) {
        if (start > end) return true;
        // 根 大于上限、小于下限 则说明非法
        if (postorder[end] > toplimit || postorder[end] < lowerlimit) return false;
        // 左右子树是否合法由左右子树自己判断,根只判断自己结点是合法的
        // 因为没必要帮孩子判断他们是否合法,因为越下去上下限是越严格的
        for (int i = start; i <= end; i++) {
            // 找到第一个大于根节点的值，划分左右子树
            if (postorder[i] > postorder[end]) {
                // 左子树
                boolean left = verifyPostorder(postorder, start, i - 1, lowerlimit, postorder[end]);
                // 右子树
                boolean right = verifyPostorder(postorder, i, end - 1, postorder[end], toplimit);
                return left && right;
            }
        }
        // 说明没有右子树,只有左子树
        return verifyPostorder(postorder, start, end - 1, lowerlimit, postorder[end]);
    }
}