Java递归解法：判断是不是二叉树后序遍历

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

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length <=1)return true;
        return verifyPostorder(0, postorder.length -1, postorder);


    }

    //最后一位是root , 先遍历数组，找到比root 大的值，然后就是 右子树了
    // 从0 开始到第一个比root 大的值减1 就是左子树。
    // 判断左子树的值是不是比root 小，已经判断了，判断右子树的值是不是都比root 大，不是，false
    //递归的去判断 左子树和右子树；

    private boolean verifyPostorder(int i , int j, int[] postorder){
        //递归结束条件
        if(i >= j){
            return true;
        }

        //寻找第一次  右子树的开始位置
        while(i < j && postorder[i]< postorder[j]){
            i++;
        }
        int index = i;

        // 左子树， 0，i-1，   右子树， i， jj
        //去看右子树是不是都大于root;数组最后一位
        while(index<j){
            if(postorder[index] < postorder[j]){
                return false;
            }
            index ++;
        }

        return verifyPostorder(0, index -1, postorder ) && verifyPostorder(index,j -1, postorder);//j已经是root， 这里是j-1;
    } 

}

这题详细讲一下，递归的思想：

后续遍历： 左 - 右 - 中

二叉搜索树： 左< 中 < 右

1. 一个数组里面，最后一位就是root , 根节点。
2. 可以把数组化为三部分。 左 | 右 | 根
3. 先假设是二叉搜素树，那么左子树都<<<<根， 开始遍历数组，直到找到第一个比根大的数，那么这个数就是右子树部分了。记录这个下标index
4. 这个时候判断，右子树是不是都大于root ,如果不是都大于，则不是二叉搜索树，返回false;

把左子树右子树，又可以用1234的逻辑做一遍，就是递归了

递归结束条件就是i>j

大家加油：P