题目描述

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

分析

找住二叉查找树的特点：左子树<根<=右子树 使用分治思想

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        if(sequence.length==1){
            return true;
        }
        return judge(sequence,0,sequence.length-1);
    }
    public boolean judge(int[] a,int start,int end){
        if(start>end){
            return true;
        }
        int i=start;
        while(a[i]<a[end]){
            i++;
        }
        for(int j=i;j<end;j++){
            if(a[j]<a[end]){
                return false;
            }
        }
        return judge(a,start,i-1) && judge(a,i,end-1);
    }
}

总结

• 二叉搜索树

  
  1.jpg
• 递归结束条件
  本题的递归结束条件是if(start >= end) { return true; } ，这一步很关键
  第一种 全是右子树 i=start 调用最后的judge 左子树直接返回true 右子树递归递归最后root-1=i=start return true
  第二种 全是左子树i=root最后的judge左子树递归递归 最后root-1=start返回true 右子树直接返回true
  第三种 左子树右子树都有正常递归 继续直到进入前面两种情况之一

参考

牛客网