题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
示例1
输入：[4,8,6,12,16,14,10]
返回值：true

题目分析

首先，二叉搜索树的特点是根节点左边的值要比根的值小，右边的值要比根的值大。
二叉搜索树的中序遍历序列是一个递增的序列（根左节点值 < 根的值 < 根右节点值）;
二叉搜索树的先序遍历序列的顺序是（根，根左节点，根右节点）；
二叉搜索树的后序遍历序列的顺序是（根左节点，根右节点，根）；
比如：二叉搜索树 [10,5,12,4,7]
图片说明
先序遍历结果为：[10,5,4,7,12]
中序遍历结果为：[4,5,7,10,12]
后序遍历结果为：[4,7,5,12,10]

解题思路

二叉树后序遍历序列的特点是：根结点在序列的最后；
1.根据根结点的值，可以将前面的数组分成左、右子树部分（左子树部分比根的值小，右子树部分比根的值大）；
2.左右子树范围内的数据若是不满足条件，则不是后序遍历序列；
若是满足，则要继续比较子树内的数值范围；
3.直到子树为空或者是只有一个结点，则比较结束，所有子树比较结果相与的值为true，则是后序遍历序列。
解题过程，如图
1.根据根节点10，可以将前面的数组分成[4,7,5][12]两个部分为left和right，且范围内数据符合要求；
图片说明
2.对[4,7,5]部分继续分解，以该部分的最后一个值5作为根节点，将其分为[4],[7]作为left和right部分，且范围内数据符合要求，因为[12]部分只有一个数，所以不用分解；
图片说明
3.当分解的部分数据都只有一个时，分解结束，每个部分都是符合要求的，所以返回true。

代码实现

方法一：递归实现

public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return VerifySquenceOfBST2(sequence, 0, sequence.length-1);
    }

    public boolean VerifySquenceOfBST2(int[] seq,int start,int end){
        if(start >= end){
            return true;
        }
        int root = seq[end];
        int i = 0;
        // 判断出左右子树的分叉点
        for(;i<end;++i){ 
            // 从数组左边开始比较，直到碰到一个比根值大的（说明是右子树部分）
            if(seq[i]> root){
                break;
            }
        }
        // 判断右子树部分的数据的合法性
        int j = i;
        for(;j<end;++j){ 
            // 若是右子树中存在比根值小的数，则不合法
            if(seq[j] < root){ 
                return false; 
            } 
        }
        // 递归判断左子树是不是二叉树 
        boolean left=true; 
        if(i> start){
            left = VerifySquenceOfBST2(seq, start, i-1);
        }
        // 递归判断右子树是不是二叉树
        boolean right = true;
        if(i < end){
            right = VerifySquenceOfBST2(seq, i, end -1);
        }
        return (left && right);
    }

代码分析：递归方法的优点是容易理解，写起来比较简单；
递归需要在遍历数组的基础上，再分成两部分遍历，时间复杂度为O(nlogn)，空间复杂度O(n);

方法二：使用单调栈

倒序遍历序列，此时的结点顺序为（根结点-右子结点-左子结点），将根结点和右子结点都放入栈中，若是碰到了左子节点（比栈顶数据小的结点值），则出栈，放入左子节点值（相当于更新了剩下的结点的最大范围），后面的值若是比最大范围大，则返回false；

public boolean VerifySquenceOfBST(int [] sequence) {
        // 借助辅助栈
        Stack<integer> stack = new Stack<>();
        // root用于保存结点的最大范围
        int root = Integer.MAX_VALUE;
        // 从右往左遍历，遍历顺序为（根-右-左）
        for(int i = postorder.length - 1; i >= 0; i--) {
            // 若后面结点大于最大范围，则不合法
            if(postorder[i] > root) return false;
            // 维持单调增栈，碰到比栈顶小的数，则不断出栈，直到栈中数据都小于结点值
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                // 这里会不断更新后面结点的最大值范围
                root = stack.pop();
            // 将结点值放入栈中
            stack.add(postorder[i]);
        }
        return true;
}

代码分析：单调栈的缺点比较难理解，优点是时间复杂度低；
时间复杂度O(n)，空间复杂度O(n)。