剑指offer代码解析——面试题24二叉搜索树的后序遍历序列

本题有bug,欢迎大神指教!

/**
 * 题目:输入一个整数数组,判断该数组书不是某二叉搜索数的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不重复。
 * @author 大闲人柴毛毛
 * @date 2016年3月15日
 */
public class SearchTree {
	/**
	 * 分析:看过题目后本题最直观的思路就是通过后序遍历序列还原这棵二叉树,然后判断该二叉树是否为二叉搜索树。
	 * 然而学过数据结构就会知道,如果给一棵二叉树的中序遍历和后序遍历序列,就能唯一确定一棵二叉树。
	 * 但本题只给了后序遍历序列,因此无法唯一确定这棵树。
	 * 那么,我们能否通过后序遍历序列把所有可能的二叉树都罗列出来,然后从中寻找是否有二叉搜索树存在。
	 * 这种穷举的方法需要时间、空间的开销都很大,这显然不是种好方法。
	 * 下面,我们从二叉搜索树和后序遍历这两个条件入手,探寻二叉搜索树的后序遍历序列的特点。
	 */
	
	/**
	 * 后序遍历的特点:由于后序遍历先访问左子树,再访问右子树,最后访问根结点,因此根结点一定在序列的末尾。
	 * 二叉搜索树的特点:二叉搜索树的左子树上所有结点均小于根结点,右子树上所有结点均大于根结点。
	 * 把这两个特点结合起来我们可以得出以下结论:在二叉搜索树的后序遍历序列中,根结点一定在序列末尾,且前半段的所有结点均小于根结点,后半段的所有结点均大于根结点。
	 * 因此,可以采用递归。按照上述方法不断划分序列,直到序列长度小于等于3时不再划分,且作如下判断:
	 * 1.若当前序列长度等于3,则表示当前序列为一棵具有三个结点的二叉搜索树,因此第一个结点必小于第三个结点,第二个结点必大于第三个结点。若不满足这个条件则无法组成一棵二叉搜索树。
	 * 2.若当前序列长度等于2,则表示当前序列为一棵具有两个结点的二叉搜索树,因此第二个结点为根结点,第一个结点可能是左子树,也可能是右子树,因此这两个结点不管谁大谁小都可以组成一棵二叉搜索树。
	 */
	
	/**
	 * 判断输入的后序遍历序列能否构成一棵二叉搜索树
	 * @param a 后序遍历序列
	 * @param start 序列起始下标
	 * @param end 序列结束下标
	 * @return 返回判断的结果
	 */
	public static boolean isSearchTree(int[] a,int start,int end){
		//若数组为空
		if(a==null || a.length<=0){
			System.out.println("后序遍历序列为空!");
			return false;
		}
		
		//若下标越界
		if(start<0 || end>=a.length){
			System.out.println("start、end越界!");
			return false;
		}
		
		//若当前序列长度为3
		if(end-start==2){
			System.out.println("当前序列长度=3……");
			//第一个结点必需要小于第三个结点,第二个结点必须要大于第三个结点,否则就无法构成二叉搜索树
			if(a[start]>a[end] || a[start+1]<a[end])
				return false;
			else
				return true;
		}
		
		//若整棵树只有一个结点、当前序列长度为2直接返回true
		else if(end-start<=1){
			System.out.print("当前序列长度<3……");
			for(int x=start;x<=end;x++)
				System.out.println(a[x]+",");
			return true;
		}
		
		//若当前序列长度超过3,则继续分隔本序列
		else{
			System.out.print("当前序列长度>3……");
			for(int x=start;x<=end;x++)
				System.out.println(a[x]+",");
			//获取末尾的根结点
			int root = a[end];
			//寻找根的左子树与右子树的分界点
			int i=start;
			while(i<end && a[i]<root)
				i++;//i停止时得到的是后半段的起点
			//判断后半段结点是否都大于根结点
			for(int j=i;j<end;j++){
				if(a[j]<root)
					return false;
			}
			//若后半段的结点均大于根结点,则进行进入递归
			//判断前半段是否为二叉搜索树的后序遍历序列
			//若当前序列均大于根结点
			boolean result_tail = true;
			boolean result_pre = true;
			if(start>end)
				result_tail = isSearchTree(a,start,end-1);
			else{
				result_pre = isSearchTree(a,start,i-1);
				//判断后半段是否为二叉搜索树的后序遍历序列
				result_tail = isSearchTree(a,i,end);
			}
			if(result_pre && result_tail)
				return true;
			return false;
		}
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		int[] a = {5,7,6,9,11,10,8};
		System.out.println("5,7,6,9,11,10,8:"+isSearchTree(a,0,a.length-1));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

37411
来自专栏Java 源码分析

ArrayList 源码分析

ArrayList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所...

3134
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1705
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

741
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

2899
来自专栏nnngu

Java中ArrayList与LinkedList的区别

Java中ArrayList与LinkedList的区别 一般大家都知道ArrayList和LinkedList的区别:       1. ArrayList的...

3606
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

2933
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1372
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3133
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2117

扫码关注云+社区