剑指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

相关文章

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1