【上海校区】二叉搜索树（BST）的后序遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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
版权声明：本文为博主原创文章，转载请附上博文链接！