剑指offer:(23)举例让抽象问题具体化 :二叉搜索树的后序遍历序列

本文主要是介绍剑指offer:(23)举例让抽象问题具体化 :二叉搜索树的后序遍历序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

二叉树搜索树就是二叉排序树,所有节点的左子树都小于它,右子树都大于它

解法:递归法

          非递归法

package co.com.jianzhioffer;public class Solution24 {/** 非递归  非递归也是一个基于递归的思想: 左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,right部分的* 最后一个数字是右子树的根他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件* 即可,即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理* 对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树 只需看看右子树的右子树是否符合要求即可*//** public boolean VerifySquenceOfBST(int[] sequence) { int size =* sequence.length; if(size==0) return false;* * int i = 0; while(--size!=0){ while(sequence[i++]<sequence[size]);* while(sequence[i++]>sequence[size]);* * if(i<size) return false; i=0; } return true; }*//** 递归方式* BST的后序序列的合法序列是,对于一个序列S,最后一个元素是x (也就是根),* 如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,* 且这两段(子树)都是合法的后序序列。完美的递归定义 : */public boolean VerifySquenceOfBST(int[] sequence) {if (sequence.length == 0)return false;return judge(sequence, 0, sequence.length - 1);}private boolean judge(int[] sequence, int l, int r) {
//		if(l>=r) return true;
//		int mid = l;
//		while(sequence[mid++]<sequence[r]&&mid<r);
//		
//		int tmp = mid;
//		while(sequence[tmp++]>sequence[r]&&tmp<r);
//		
//		if(tmp<r){
//			return false;
//		}
//		
//		if(mid==l || tmp==r){
//			return judge(sequence, l, r-1);
//		}else{
//			return (judge(sequence,l,mid-1)&&judge(sequence, mid+1, r-1));
//		}if(l>=r) return true;int i = r;//以右子树的条件,找到左子树的根i-1while(i>l&&sequence[i-1]>sequence[r]) --i;//判断左子树是否都小于根for(int j=i-1;j>=l;--j) if(sequence[j]>sequence[r]) return false;return judge(sequence, l, i-1) && judge(sequence, i, r-1);}
}


这篇关于剑指offer:(23)举例让抽象问题具体化 :二叉搜索树的后序遍历序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/581078

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码