文档章节

剑指Offer(Java版):二叉搜索树的后序遍历序列

一贱书生
 一贱书生
发布于 2016/07/23 14:39
字数 1389
阅读 50
收藏 0

题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

例如输入数组{5,7,6,9,11,10,8}则返回true,因为这个整数序列是下图二叉树的后序遍历的结果。如果输入的数组是{7,4,6,5},由于没有哪颗二叉搜索树的后续遍历的结果是这个序列,因此返回false。

在后序遍历得到的序列中,最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值,它们都比根节点的值小;第二部分是右子树结点的值,他们都比根节点的值大。

以数组{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是根节点的值。在这个数组中,前3个数字5,7和6都比8小,是值为8的结点的左子树结点;后3个数字9,11和10都比8 大,是值为8的结点的右子树结点。

我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实 就是一个递归的过程。对于序列5,7,6,最后一个数字6是左子树的根节点的值。数字5比6小,是值为6的结点的左子结点,而7则是它的右子节点。同样, 在序列9,11,10中,最后一个数字10是右子树的根节点,数字9比10小,是值为10的结点的左子结点,而11则是它的右子节点。

我们再来分析一下另一个数组{7,4,6,5}。后序遍历的最后一个 树是根节点,因此根节点的值是5.由于第一个数字7比5大,因此对应的二叉搜索树中,根节点上是没有左子树的,数字7,4,和6都是右子树结点的值。但我 们发现在右子树中有一个结点的值是4,比根节点的值5小,这违背了二叉搜索树的定义。因此不存在一颗二叉搜索树,它的后序遍历的结果是7,4,6,5.

Java代码实现为;

package cglib;

public class DeleteNode {
    public boolean verifySequence(int[] array,int start,int end) throws Exception{  
        if(array == null || array.length < 2)  
            return true;  
        if(start < 0){  
            throw  new Exception("first can't be less than 0");  
        }  
        if(end > array.length){  
            throw new Exception("last can't be greater than the count of the element.");  
        }  
        int root = array[end];  
        //在二叉搜索树中左子树的结点小于根节点  
        System.out.println("根节点array["+end+"]="+array[end]);
        int i = start;  
        for(; i < end;i++){
            System.out.println("比较前array["+i+"]="+array[i]);
            if(array[i]>root){//576这三个数都过去
               System.out.println("比较后array["+i+"]="+array[i]);
                break;
        }
        }  
        //在二叉搜索树中右子树的结点大于根节点  
        int j = i;  
        for(;j < end;j++){
            System.out.println("比较前array["+j+"]="+array[j]);
            if(array[j] < root){
                System.out.println("比较后array["+j+"]="+array[j]);
                return false;
            }
        }  
        //判断左子树是不是二叉搜索树  
        boolean left = true;  
        if(i >start)  
            left =verifySequence(array ,start,i-1);  
        //判断右子树是不是二叉搜索树  
        boolean right = true;  
        if(i < end)  
            right = verifySequence(array,i,end-1);  
        return (left && right);  
    }  
    public static void main(String[] args) throws Exception{  
        int[] arr={5,7,6,9,11,10,8};  
        DeleteNode test = new DeleteNode();  
        System.out.println(test.verifySequence(arr, 0, arr.length-1));  
    }  
}

 

输出:

根节点array[6]=8
比较前array[0]=5
比较前array[1]=7
比较前array[2]=6
比较前array[3]=9
比较后array[3]=9
比较前array[3]=9
比较前array[4]=11
比较前array[5]=10
根节点array[2]=6
比较前array[0]=5
比较前array[1]=7
比较后array[1]=7
比较前array[1]=7
根节点array[0]=5
根节点array[1]=7
根节点array[5]=10
比较前array[3]=9
比较前array[4]=11
比较后array[4]=11
比较前array[4]=11
根节点array[3]=9
根节点array[4]=11
true

拓展: 输入一个整数数组,判断该数组是不是某二叉搜索树的前遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

前序遍历,则第一个数组的数就是根节点

package cglib;

public class DeleteNode {
    public boolean verifySequence(int[] array,int start,int end) throws Exception{  
        if(array == null || array.length < 2)  
            return true;  
        if(start < 0){  
            throw  new Exception("first can't be less than 0");  
        }  
        if(end > array.length){  
            throw new Exception("last can't be greater than the count of the element.");  
        }  
        //int root = array[start];  
        //在二叉搜索树中左子树的结点小于根节点  
        System.out.println("根节点array["+start+"]="+array[start]);
        int i = start+1;
        
        for(; i < end;++i){
            System.out.println("i比较前array["+i+"]="+array[i]);
            if(array[i]>array[start]){//657这三个数都过去,1,2,3
               System.out.println("i比较后array["+i+"]="+array[i]);
                break;
        }
        }
        boolean left=true;
        boolean right=true;
        
        if (i < end)  
        {    //判断左子树是不是二叉搜索树  
             left = verifySequence(array, start + 1, i - 1);
           //判断右子树是不是二叉搜索树
             right = verifySequence(array, i, end);  
        }  
        for (; i <= end; ++i)  
        {   //在二叉搜索树中右子树的结点大于根节点  
            if (array[i] < array[start])  
                return false;  
        }  
        
        return left && right;
        
        
    }  
    public static void main(String[] args) throws Exception{  
        int[] arr={8,6,5,7,10,9,11};  
        DeleteNode test = new DeleteNode();  
        System.out.println(test.verifySequence(arr, 0, arr.length-1));  
    }  
}

输出:

根节点array[0]=8
i比较前array[1]=6
i比较前array[2]=5
i比较前array[3]=7
i比较前array[4]=10
i比较后array[4]=10
根节点array[1]=6
i比较前array[2]=5
根节点array[4]=10
i比较前array[5]=9
true

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
2018/07/11
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
0
0
剑指offer java版(三)

二叉搜索树的后序遍历 问题描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路 对于后...

Android机动车
03/22
0
0
[剑指offer] 二叉搜索树的后序遍历序列

题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路 二叉搜索树: 左子树

繁著
2018/07/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

泛型就这么简单

前言 从今天开始进入Java基础的复习,可能一个星期会有一篇的<十道简单算法>,我写博文的未必都是正确的~如果有写错的地方请大家多多包涵并指正~ 今天要复习的是泛型,泛型在Java中也是个很...

群星纪元
37分钟前
3
0
大数据提醒你:中国这些古建筑,可能是下一个巴黎圣母院!

大家晚上好,我是今天的提笔人嗅嗅。 巴黎圣母院失火事件让我的心情很沉重,一句无关痛痒的安慰“巴黎不哭”,已经不能表达我对这场文化之殇的惋惜之痛,人类伟大的建筑在一瞬间被毁灭。 世界...

forespider
48分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index(“待截取的字符串”,“截取数据依据的字符”,截取字符的位置N) 第三个参数可正,可负。正数表示索引字符前面的字符串,负数...

echojson
48分钟前
2
0
好程序员web前端分享用CSS和JS打造一个简单的图片编辑器

好程序员web前端分享用CSS和JS打造一个简单的图片编辑器,本文主要是利用CSS的 filter和简单的Jquery代码来实现一个简单的图片编辑器,包括对图片的透明度,黑白,图片亮度等调节。 CSS filt...

好程序员IT
58分钟前
2
0
浅析spring mvc的细节

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

最爱肉肉
59分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部