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

参考链接

剑指offer_在线编程 - 牛客网

剑指 Offer 33. 二叉搜索树的后序遍历序列-跟着帅地玩转校招，刷爆各类算法题 - 帅地玩Offer

LCR 152. 验证二叉搜索树的后序遍历序列 - 力扣（LeetCode）

优秀题解

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        // 注意：记得写终止条件！
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solutions/150225/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

刚开始还以为需要通过后序遍历还原二叉搜索树，倒腾了半天也没思路...

优秀题解思路

递归分治，将问题分解为 与原问题形式相同的 子问题，递归求解，求解完合并即可

1、找到数组最后一个元素，即 根节点（后序遍历，左右中）

2、根据 二叉搜索树（左 < 中 < 右）的性质，找到第一个大于根节点的索引

3、依据找到的索引将数组分成两半，左区间 需要 满足小于根节点，右区间需要满足大于根节点

4、遍历数组，倘若有元素不满足 规则3 则返回 false，否则 继续分解问题

5、将问题划分为 子问题，递归检索 子问题 的 子区间 是否符合规则

6、所有子问题都正确，返回 true