题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 分析 后序遍历序列中,最右边数字也就是根结点,会把数集分为左右两部分,左边数集都小于root,右边数集都大于root。左边数集和右边数集与原数集一样,所以可以用递归来做。 代码 public class BSTOrder { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = {1,2,3,5,6,4,8,10,9,7}; //非递归方法实现递归思想 int len = arr.length-1; int i=0; while(len!=0){ while(arr<arr[len]){ i++; } while(arr>arr[len]){ i++; } if(i<len){ System.out.println(false); return; } len--; i=0; } System.out.println(true); System.out.println(fun(arr, 0, len-1));; } //递归方法 public static boolean fun(int[] arr, int l, int r){ if(l >=r){ return true; } int i=r; //找到小于root和大于root数集的的边界,到最后i为小于root的数中最右边的那个 while(i>l && arr[i-1]>arr[r]){ i--; } //左边数集(left)应该都小于root for(int j=i-1; j>=l; j--){ if(arr[j]>arr[r]){ return false; } } //左子树(left)与右子树(right)的情况 return fun(arr, l, i-1) && fun(arr, i, r-1); } } --------------------- 作者:另一个我竟然存在 来源:CSDN 原文:https://blog.csdn.net/qq_24034545/article/details/84110567 版权声明:本文为博主原创文章,转载请附上博文链接! |