JZ23_二叉搜索树的后序遍历序列（有待优化）.md

JZ23_二叉搜索树的后序遍历序列

这题写的不好，思路比较乱，大致是：递归从右往左找到分界点，因为二叉搜索树满足左子小于根，右子大于根，找到分界点后，先继续遍历判断分界点两侧的元素值，是否满足左边小且右边大，再对两棵子树继续递归，递归过程有待优化

public boolean VerifySquenceOfBST(int [] sequence) {
        //其中一组样例得知，若为空，则false
        if (sequence.length == 0) return false;
        return solve(sequence, 0, sequence.length-1);
    }

    //如果我的形参中有数组类型，本质上对堆内存的消耗没有增多，但是递归会消耗大量的栈内存
    public boolean solve(int[] a, int left, int right) {
        //如果左边界大于右边界 比如没有元素情况下 left=0 ，right=-1
        //又或者只有一个数则不分左右
        if (left >= right)
            return true;
        else {
            //temp表示分界线
            int temp = right;
            for (int i = right; i >= left; i--) {
                if (a[i] < a[right]) {
                    temp = i;
                    break;
                }
            }
            //当不是最右侧节点为根节点时
            if (temp != right) {
                //如果在分界线左侧还有比a[right]大的则表示不符合二叉排序树的规则
                for (int i = temp-1; i >= left; i--) {
                    if (a[i] > a[right])
                        return false;
                }
                //如果能执行到这里说明需要继续细分
                return solve(a, 0, temp) && solve(a, temp+1, right-1);
            } else {//这里只需要单侧
                return solve(a, 0, temp-1);
            }
        }
    }