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

python 未结 0 64
整合网络营销
整合网络营销 2021-07-22 15:26
悬赏:49
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复