剑指offer-面试题24：二叉搜索树的后序遍历序列_Decorator2015的博客-程序员秘密

题目

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

解

package Chapter4;

public class VertifySquenceOfBST {
    

    boolean vertifySquenceOfBST(int[] sequence,int start,int end){

        if(sequence==null||start>end){
            return false;
        }

        int root=sequence[end];

        //在二叉搜索树中左子数的结点小于根结点
        int i=start;
        for(;i<=end-1;i++){
            if(sequence[i]>root)
                break;
        }

        //在二叉搜索树中右子树的结点大于根结点
        int j=i;
        for(;j<=end-1;j++){
            if(sequence[j]<root){
                return false;
            }
        }

        //判断左子树是不是二叉搜索树
        boolean left=true;
        if(start<i-1)
            left=vertifySquenceOfBST(sequence,start,i-1);

        //判断右子树是不是二叉搜索树
        boolean right=true;
        if(i<end-1)
            right=vertifySquenceOfBST(sequence,i,end-1);

        return (left && right);


    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        VertifySquenceOfBST  vS=new VertifySquenceOfBST();
        int[] sequence={
   5,7,6,9,11,10,8};
        int[] sequence2={
   7,4,6,5};
        System.out.println("sequence :"+vS.vertifySquenceOfBST(sequence, 0,sequence.length-1));
        System.out.println("sequence2 :"+vS.vertifySquenceOfBST(sequence2, 0,sequence2.length-1));

    }

}

本文链接：https://blog.csdn.net/Decorator2015/article/details/51719667

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

iOS回顾笔记（04） -- UIScrollView的基本使用详解_weixin_30755709的博客-程序员秘密

iOS回顾笔记（04） -- UIScrollView的基本使用详解前言本文主要讲述了 UIScrollView 的一些常用的属性和方法、引申了delegate的思想和UIScrollView的缩放。这篇文章着重介绍UIScrollView的基本知识，关于UIScrollView的实例使用我会在下一篇iOS回顾笔记（05）中着重讲解。UIScrollViewU...

Vue——过渡和动画1_小志的博客的博客-程序员秘密

1、代码<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>过渡&动画1</title> <style> /*显示、隐藏的过度效果*/ .fade-enter-active,.fade-le...

C/C++静态库与动态库（Clion下创建及调用静态库）_c/c++ 动态链接库项目创建 clion_Phantom_matter的博客-程序员秘密

文章目录静态库动态库Clion创建及调用静态库创建一个C静态库对于生成的工程构建项目这两个文件会在调用的时候用到新建一个C工程，创建两个文件夹（在工程里），将刚才的两个文件放进去：对cmakelists.txt 进行修改运行结果库是现有的，已经写好的，可以复用的代码。本质上来说库是一种可执行代码的二进制形式，可以被操作系统载入内存执行。库有两种：静态库（.a、.lib）和动态库（.so、.dll）。所谓静态、动态是指链接。回顾一下，将一个程序编译成可执行程序的步骤：静态库之所以成为【静态库】，是

sci分类_sci kit学习中的整体投票分类器和随机森林_weixin_26729283的博客-程序员秘密

sci分类Let us say you pose a complex question to a set of random people and collect the answers in to a data set. Now, you aggregate (take average of) all the answers present in the dataset , Many a tim...

阿里巴巴Java 约规手册：码出高效，码出质量_码出高效码出质量_wangbo818的博客-程序员秘密

最近在和实验室的同学一起给学校教务处做一个教学工作量统计系统，在团队一起合作开发及测试的过程中，我认识到了自己在开发规范方面的不足，虽然以前就看过阿里巴巴Java 约规手册，但是我在平时自己做项目、学习的过程中并没有很注意，只遵守驼峰命名等较为基础的约规。在这次的开发过程中，因为开发当中的不规范而导致了很多问题，例如：POJO 类及方法返回值的类型都定义的是 int 等基本类型，而不是 Int...

intellij idea 设置项目more的jdk和编码格式_ChanYeeLi的博客-程序员秘密

1.设置默认jdk file–other setting–default project structure– 在右侧选择jdk版本 2.设置编码格式 file–other setting–default setting–editor–file encoding–右侧设置编码格式