专栏首页用户7745800的专栏Day23:二叉搜索树的后序遍历序列

Day23:二叉搜索树的后序遍历序列

剑指Offer_编程题——二叉搜索树的后序遍历序列

题目描述:

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

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

背景知识介绍   在做此题时,我们应该熟练掌握二叉搜索树的相关知识,首先我们定义二叉搜索树:在二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:   若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;   若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;   任意节点的左、右子树也分别为二叉查找树;   二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(logn)二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、多重集、关联数组等。二叉查找树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列,一个无序序列可以透过建构一棵二叉查找树变成一个有序序列,建构树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索、插入、删除的复杂度等于树高,虽然二叉查找树的最坏效率是O(N),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为O(logn)。 例如以下就是一颗搜索二叉树:

  由上面介绍的二叉搜索树的相关概念可知,对于一个二叉树的后序遍历序列来说,最后一个数一定是根节点,然后前面的数中,从最开始到第一个大于根节点的数都是左子树中的数。而后面的倒数第二个数应该大于根节点的,是右子树,如果后面的数中有小于根节点的,那么说明这个序列不是二叉搜索树的后序遍历序列。具体可以利用从左遍历找到第一个比根节点的大的位置划分左右节点,这样保证了左边部分都比根节点小,不能保证右边部分都比根节点大,所以对右边的部分进行了验证。我们具体可以通过python和java来实现。 1、首先我们用java来将其实现:

import java.util.Arrays;
public class Solution{
	public boolean VerifySquenceOfBST(int [] sequence){
		if(sequence == null || sequence.length <= 0){
			return false;
		}
		int len = sequence.length;
		int root = sequence[len - 1];
		int i = 0;
		for(; i < len - 1; i++){
			if(root <= sequence[i]){
			     break;
			}
		}
		int j = i;
		for(; j < len - 1; j++){
			if(root > sequence[j]){
				return false;
			}
		}
		boolean leftFlag = true;
		if (i > 0){
			leftFlag = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
		}
		boolean rightFlag = true;
		if(i < len - 1){
			rightFlag = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length - 1));
		}
		return leftFlag && rightFlag;
	}
}

代码测试效果图如下:

2、接下来用python来实现

class Solution:
	def VerifySquenceOfBST(self, nums):
		if not nums:
			return False
		return self.verifyBST(nums)
	def verifyBST(self, nums):
		if not nums:
			return True
		root = nums.pop()
		index = self.findIndex(nums, root)
		if self.verifyRight(nums[index:], root):
			left = nums[:index]
			right = nums[index:]
			return self.verifyBST(left) and self.verifyBST(right)
		return False
	def verifyRight(self, nums, target):
		if not nums:
			return True
		return min(nums) > target
	def findIndex(self, nums, target):
		for i, num in enumerate(nums):
			if num > target:
				return i
		return len(nums)

代码效果图如图所示:

总结

  本道题是通过搜索二叉树来判断一个序列的是不是搜索二叉树的后序遍历,因此,这道题需要了解搜索二叉树的特性。并且都知道它的后序遍历是有序的,并且我们根据其独特的特性进行判断即可。因此,我们尽可能用多的方法以及多的用不同语言将其实现,这样才能做到多种语言的融会贯通。总之,我们要继续加油,争取早日找到工作,Good Luck!!!

参考文献:

[1] 二叉搜索树 [2] qq_23217629 [3] 负雪明烛

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day66:机器人的运动范围

    背景知识介绍:   在做题之前,首先给大家介绍数据结构中典型的两种遍历方式:深度优先遍历以及广度优先遍历。图的遍历是指从图中的任一顶点出发,对图中的所有顶点访...

    stefan666
  • 数据分析(一)——数据分析思维

      上篇文章我们初步介绍了数据分析的概要,大概从数据分析现在的应用现状、数据分析的概念、数据分析的分析方法、为什么要学习数据分析以及数据分析的结构层次等几方面给...

    stefan666
  • Day29:最小的K个数

    思路   我们看题意可知,今天的题目和上一道题比较的类似,上一道题是将数组中重复数字次数超过数组长度一半输出来这个数字。而今天的的数字是输出最小K个数。都是要...

    stefan666
  • 学界 | DeepMind解密黑箱的第一步:原来神经网络的认知原理和人类是一样的!

    AI 科技评论按:因为AlphaGo而名声大噪的人工智能公司DeepMind近期发表了一篇论文介绍自己在神经网络的解释性问题上最新探索。论文被ICML接受后,D...

    AI科技评论
  • Java微信公众平台开发(十一)--微信JSSDK中Config配置 (一)在微信公众平台绑定安全域名(二)后端接口实现JS-SDK配置需要的参数 (三)页面实现JS-SDk中con

    JSSDK曾经引爆前端以及后端的工程师,其魔性的力量毋庸置疑,在我们的技术眼里它的实现原理和根本是不能够被改变的,这篇文章就不对其js的实现做任何评价和解说了(...

    用户2417870
  • Python 实战(5):拿来主义

    有了列表,有了详细信息,有了搜索,这个电影网站已经有了基本的结构。现在要做的是:获取更多的内容。 我们没有必要也不可能自己去生产数量庞大的电影信息,互联网上的资...

    Crossin先生
  • ICML论文|这违反直觉的“升噪”方法,反而能很好的解决激活函数梯度弥散的问题

    GAIR 今年夏天,雷锋网将在深圳举办一场盛况空前的“全球人工智能与机器人创新大会”(简称GAIR)。大会现场,谷歌,DeepMind,Uber,微软等巨头的人...

    AI科技评论
  • 向宇宙宣告:人类文明未来的信标(II)

    如果我们要用语言来解释我们的历史,如何做到呢?我们不可能把所发生的每一个细节都逐一阐述。我们需要提供一个更高级的符号式描述, 抓住重要部分,而理想化其他东西。当...

    WolframChina
  • Tenacity——Exception Retry 从此无比简单

    Python 装饰器装饰类中的方法这篇文章,使用了装饰器来捕获代码异常。这种方式可以让代码变得更加简洁和Pythonic。

    青南
  • DIY 13.8V 通信电源+直流UPS不间断电源

    开口,挖洞,我只有美工刀和电烙铁。使用电烙铁加热戳出一个洞,然后用美工刀挖。好累啊。

    netkiller old

扫码关注云+社区

领取腾讯云代金券