Java二叉搜索树的后续遍历(递归)

剑指offer 33.二叉搜索树的后序遍历

解题思路:
1. 二叉搜索树的特点:
二叉搜索树中根节点的值大于左子树中的任意一个节点的值,
小于右子树中的任意一个节点 的值
2. 后序遍历顺序: 左子树–>右子树–>根节点

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length < 2) return true;
        return verify(postorder, 0, postorder.length - 1);
    }
    public boolean verify(int[] postorder, int left, int right){
        //说明数组元素 <= 1
        if(left >= right) return true;
        //从后序遍历可知,数组最后一个元素为根节点
        int root = postorder[right];
        int k = left;
        //从后序遍历可知,
        //第一个大于根节点的 节点 之后的 所有节点 都大于根节点
        //让指针 k 从数组最开始遍历,找出第一个大于根节点的节点
        while(k < right && postorder[k] < postorder[right]){
            k++;
        }
        //从第一个大于根节点的节点开始遍历
        //判断之后出现的节点的值是否都大于根节点的值
        //出现小于根节点的情况,直接返回false
        for(int i = k; i < right; i++){
            if(postorder[i] < root) return false;
        }
        //检查左子树
        if(!verify(postorder, left, k - 1)) return false;
        //检查右子树
        if(!verify(postorder, k, right - 1)) return false;
        return true;
    }
}