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


相关推荐

  • index() 方法返回指定元素相对于其他指定元素的 index 位置。

    index() 方法返回指定元素相对于其他指定元素的 index 位置。

    2021年10月18日
  • Eclipse没有server 配置Tomcat「建议收藏」

    Eclipse配置Tomcat服务器如果你的Eclipse没有server,请查看:http://blog.csdn.net/guyuealian/article/details/50762996【1】下载并成功安装了Eclipse和Tomcat:(1)Tomcat下载地址:http://tomcat.apache.org/(尽量安装6.0以上的版本)(2)Eclip

  • mysql数据库同步工具_mysql同步工具_mysql数据库同步

    mysql数据库同步工具_mysql同步工具_mysql数据库同步 下载网站:www.SyncNavigator.CN  客服QQ1793040———————————————————-  关于HKROnlineSyncNavigator注册机价格的问题HKROnlineSyncNavigator 8.4.1企业版数据同步软件自2009年第一个版…

  • leapFTP上传网页到服务器,leapftp登录ftp服务器

    leapFTP上传网页到服务器,leapftp登录ftp服务器leapftp登录ftp服务器内容精选换一换本节为您介绍如何在本机使用远程登录工具MSTSC登录Windows弹性云服务器。弹性云服务器状态为“运行中”。如果弹性云服务器采用密钥方式鉴权,已获取Windows弹性云服务器的密码,获取方式请参见获取Windows弹性云服务器的密码。弹性云服务器已经绑定弹性公网IP,绑定方式请参见绑定弹性公网IP。使用MSTSC方式通过内网登录云服务器华为云帮助中心…

    2022年10月24日
  • 利用STM32F103精确控制步进电机

    利用STM32F103精确控制步进电机**利用STM32F103控制步进电机精确角度转动**欢迎使用Markdown编辑器你好!这是你第一次使用Markdown编辑器所展示的欢迎页。如果你想学习如何使用Markdown编辑器,可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,…

  • 415错误代码

    415错误代码检查错误1.前端是否为json传递2.后端是否导入了包<dependency><groupId>com.fasterxml.jackson.dataformat</groupId><artifactId>jackson-dataformat-xml</artifactId><version>2.10.1</version></dependency>3.重新新后端的实体

发表回复

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

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