剑指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 条评论
登录 后参与评论

相关文章

来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

1749
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

351
来自专栏Vamei实验室

纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。 在之前的文章中,我们基于完全二叉树(complete bi...

2829
来自专栏LanceToBigData

JavaSE(八)集合之List

前面一篇的corejava讲的是集合的概述,这一篇我将详细的和大家讲解一下Collection下面的List、set、queue这三个子接口。希望大家能得到提升...

21210
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

2799
来自专栏文武兼修ing——机器学习与IC设计

树与二叉表达树树基础二叉表达树

树基础 定义 数的定义 可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一...

2646
来自专栏python学习指南

Scala入门学习笔记三--数组使用

前言 本篇主要讲Scala的Array、BufferArray、List,更多教程请参考:Scala教程 本篇知识点概括 若长度固定则使用Array,若...

19610
来自专栏老马说编程

(46) 剖析PriorityQueue / 计算机程序的思维逻辑

上节介绍了堆的基本概念和算法,本节我们来探讨堆在Java中的具体实现类 - PriorityQueue。 我们先从基本概念谈起,然后介绍其用法,接着分析实现代码...

1917
来自专栏武培轩的专栏

剑指Offer-二叉搜索树的后序遍历序列

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

3045
来自专栏木子昭的博客

Python实现深度优先与广度优先

二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归 ? 二叉树 深度优先 先序遍历(父, 左子, 右子) 0,...

3777

扫描关注云+社区