首页 > 其他 > 详细

<剑指offer> 第21题

时间:2019-08-10 22:33:20      阅读:105      评论:0      收藏:0      [点我收藏+]

题目:

输入一个整数数组,判断该数组是不是某二叉搜索树的后续遍历的结果。如果是则返回true,否则返回false

思路:

后序遍历的特点,最后一个数字为树的根节点的值,数组中前边的数字可以分为两部分,第一部分是左子树的值,都比根节点小,第二部分都是右子树的值,都比根节点大

代码:

public class TwentyFirst {

    public boolean whetherPostOrder(int[] arr){
        if(arr == null){
            return false;
        }
        return checkPostOrder(arr, 0, arr.length - 1);
    }

    public static boolean checkPostOrder(int[] arr, int start, int end){
        //如果需要处理的数据只有一个或者没有数据要处理了,就返回true
        if(start >= end){
            return true;
        }

        //从左到右找第一个不小于根节点的元素的位置
        int index = start;
        while(index < end - 1 && arr[index] < arr[end]){
            index ++;
        }
        //从第一个不小于根节点元素的位置一直到根节点的位置
        int right = index;
        while(index < end - 1 && arr[index] > arr[end]){
            index ++;
        }

        if(index != end - 1){
            return false;
        }
        
        index = right;
        return checkPostOrder(arr, start, right - 1) && checkPostOrder(arr, right, end - 1);
        
    }
}

 

<剑指offer> 第21题

原文:https://www.cnblogs.com/HarSong13/p/11332917.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!