判断一个给定数组是否为二叉搜索树后序遍历

问题：判定一给定数组是否为二叉搜索树的后序遍历结果面试题33. 二叉搜索树的后序遍历序列（递归分治 / 单调栈，清晰图解） - 二叉搜索树的后序遍历序列 - 力扣（LeetCode）

思路一：递归 数组最后一个数必为根节点 ,下标记为 j ，以此节点为左右子树的分界线，

　　从前往后遍历数组，找到第一个比根节点大的数，下标记为m；那么m之前的都是小于根节点的；[ i , m-1 ]

　　判定该下标m之后的数是否都大于根节点；并且判断最后下标是否与根节点下标相等 ，则该根节点满足条件，[ m , j -1 ]  ，

　　继续缩小范围 递归 判定左右子树是否满足，逻辑与；[ i , m-1 ] < [ m , j -1 ] ,

时间复杂度：O(N²)  ;空间复杂度：O(N)

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return recur(postorder,0,postorder.size()-1);
    }
private:
    bool recur(vector<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);
    }
};

思路二：观察倒序 + 单调栈

　　倒序：将后续遍历镜像，根--右--左；

　　　　若是递增，则说明当前节点为前一个节点的 右子节点；

　　　　若是递减，则是前面节点中，大于当前节点且是最小的 那个节点(父节点) 的左子节点，且当前节点之后的节点都小于那个父节点，若满足则为 二叉搜索树；

借此 可以辅助栈，将递增序列的节点依次压入栈中，判断当前栈顶节点与下一个当前节点大小，递增就继续压栈，

　　　　递减，栈不为空且当前节点小于栈顶元素，循环出栈顶，设置一个父节点存储栈顶，遍历完则说明满足

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int>tmp;
        int max_num = INT_MAX; 
        for(int i = postorder.size()-1;i>=0;--i){
            if(postorder[i] > max_num) return false;
            while(tmp.size() && postorder[i] < tmp.top()){
                max_num = tmp.top();
                tmp.pop();
            }
            tmp.push(postorder[i]);
        }
        return true;

    }
};