【剑指offer】二叉搜索树的后序遍历序列

【剑指offer】二叉搜索树的后序遍历序列

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

转载请注明出处:http://blog.csdn.net/ns_code/article/details/26092725


    剑指offer上的第24题,主要考察递归思想,九度OJ上AC。

题目描写叙述:

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

输入:

每一个測试案例包括2行:

第一行为1个整数n(1<=n<=10000),表示数组的长度。

第二行包括n个整数,表示这个数组,数组中的数的范围是[0,100000000]。

输出:

相应每一个測试案例,假设输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No。

例子输入:
7
5 7 6 9 11 10 8
4
7 4 6 5
例子输出:
Yes
No

    要紧紧抓住二叉搜索树的特点,对于后序遍历序列,其每一个子树的最后一个元素会比前面的左边一部分大,右边一部分小,这样便能够通过递归来推断。

    AC代码例如以下:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

bool IsBehSequenceBST(int *seq,int len)
{
	if(seq==NULL || len<1)
		return false;

	int root = seq[len-1];
	int i;
	for(i=0;i<len-1;i++)
		if(seq[i]>root)
			break;

	//第一个右子树元素的下标
	int RightStart = i;

	for(;i<len-1;i++)
		if(seq[i]<root)
			return false;
 
	bool left = true;
	if(RightStart > 0)
		left = IsBehSequenceBST(seq,RightStart);
	bool right = true;
	if(RightStart < len-1-RightStart)
		right = IsBehSequenceBST(seq+i,len-RightStart-1);

	return (left && right);

}

int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		int *seq = (int *)malloc(n*sizeof(int));
		if(seq == NULL)
			exit(EXIT_FAILURE);

		int i;
		for(i=0;i<n;i++)
			scanf("%d",seq+i);
		if(IsBehSequenceBST(seq,n))
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

/**************************************************************
    
Problem: 1367
    
User: mmc_maodun
    
Language: C
    
Result: Accepted
    
Time:70 ms
    
Memory:1308 kb
****************************************************************/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118828.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 美团面试中被问到的问题汇总

    美团面试中被问到的问题汇总

  • 小明の魔法计划——最长上升子序列[通俗易懂]

    小明の魔法计划——最长上升子序列[通俗易懂]Think:1知识点:最长上升子序列2反思:知识体系需要加深拓展SDUT题目链接小明の魔法计划TimeLimit:1000MSMemoryLimit:65536KBProblemDescription在一个遥远的数学魔法国度,小明在学习一个魔法,这个魔法需要一些施法材料,所幸的是施法材料已经准备好了,下一步就是建立魔法阵了,每一个施法材料都有一个特性值,表示为一个大于1小

  • 数据挖掘项目总结文档模板_数据挖掘实训心得

    数据挖掘项目总结文档模板_数据挖掘实训心得数据挖掘项目总结文档1、文档概述1.1编写目的记录本次实验思路及流程,备忘用。1.2适用对象个人学习总结,描述有偏差之处陆续更进。2、业务理解与分析定义2.1需求概述针对传统网络入侵检测系统存在的误判以及漏检情况,采用数据挖掘的指导思想,通过大量的攻击样本数据进行知识发现,本次实验采用的kdd99数据集,其中包含了大量的模拟攻击行为。1998年美国国防

  • SpringCloud(八)—-OpenFeign通讯优化

    SpringCloud(八)—-OpenFeign通讯优化

    2020年11月12日
  • STUN协议详解

    STUN协议详解   基于RFC3489标准的stun协议,无法穿越TCP类型NAT,只是适用于在现有NAT类型下的UDP穿越,另一种特殊情况NAT也无法进行穿越,就是对称型NAT,在很多企业中就很多属于对称型NAT,后面会讲到。STUN的发现过程是基于UDP的NAT处理的假设;随着新的NAT设备的部署,这些假设可能会被证明是无效的,当STUN被用来获取一个地址来与位于其在同一NAT后面的对等体通信时,它就不起作用了。当stun服务器的部署不在公共共享地址域范围内时,stun就不起作用。1.定义STUN客户端:产生

  • JavaFX横幅类游戏开发 教训 游戏贴图

    JavaFX横幅类游戏开发 教训 游戏贴图

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号