剑指Offer——二叉搜索树的后序遍历序列 Java

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题目解析

结合 重构二叉树题目

两道题基本一致，都是递归左右子树。

难点：在于思考清楚 左右子树的入口（左子树的范围，右子树的范围）

对于一次递归中的思路是：

先从一棵树的最左侧开始，若都小于该树的root 就向右滑动，直到遇到第一个比root大的值（左子树都应该< root）

然后再从第一个大的值开始，继续向右遍历（右子树都应该>root），若出现 小于的情况 则直接判false；

BST的后序序列的合法序列是：对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 。

题解

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

}

    public boolean helper(int []sequence,int lo ,int hi){
        // 递归出口 当lo == hi 时候表示当前节点即自己为根
        // lo > hi 时候 表示出现null 节点
        if (lo >= hi ) return  true;
        int root = sequence[hi];
        int i = lo;
        while (i < hi){
            if (sequence[i] > root) break;
            i++;
        }
        int j = i;
        while (j < hi){
            if (sequence[j] < root) return false;
            j++;
        }
        //  划清左右子树范围，递归左右子树
        return helper(sequence,lo,i-1) && helper(sequence,i,hi-1);
    }