文档章节

检查一棵二叉树是否为二叉查找树

一贱书生
 一贱书生
发布于 2016/11/18 11:01
字数 183
阅读 5
收藏 0
点赞 0
评论 0

public static int index=0;
public static copyBST(TreeNode root,int [] array)
{
if(root== null) return ;
copyBST(root.left,array);
array[index]=root.data;
index++;
copyBST(root.right,array);
}
public static boolean checkBST(TreeNode root)
{
int [] array=new int[root.size];
copyBST(root,array);
for(int i=1;i<array.length;i++)
{
if(array[i]<=array[i-1]) return false;
}
return true;
}

public static int last_printed=Integer.MIN_VALUE;
public static boolean checkBST(TreeNode n)
{
if(n==null) return true;
//递归检查左子树
if(!checkBST(n.left)) return false;
//检查当前结点
if(n.data<=last_printed) return false;
last_printed=n.data;
//递归检查右子树
if(!checkBST(n.right)) return false;
return true;//全部检查完毕
}

 

惊恐解法二:最小/最大法

boolean checkBST(TreeNode n)
{
     return checkBST(n,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
boolean checkBST(TreeNode n,int min,int max)
{
if(n==null)
return true;
if(n.data<min||n.data>max)
return false;
if(!checkBST(n.left,min,n.data)||!checkBST(n.right,n.data,max));
{
return false;
}
return true;
}

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
检查是否为BST(二叉查找树(或二叉排序树、二叉搜索树))

1、题目内容 题目描述 请实现一个函数,检查一棵二叉树是否为二叉查找树。 给定树的根结点指针TreeNode root,请返回一个bool,代表该树是否为二叉查找树。 2、题目解析 方法1:因为二叉查找...

笨拙的小Q ⋅ 2016/04/20 ⋅ 0

判断一棵二叉树是否为搜索二叉树和完全二叉树

【题目】 给定一个二叉树的头结点head,已知其中没有重复值的节点,实现两个函数分别判断这棵二叉树是否是搜索二叉树和完全二叉树。 【回顾】 二叉查找树(Binary Search Tree),(又:二叉...

junjunba2689 ⋅ 04/19 ⋅ 0

数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor ⋅ 2017/11/06 ⋅ 0

平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134 ⋅ 2017/06/03 ⋅ 0

数据结构与算法——常用数据结构及其Java实现

前言 仿佛一下子,2017年就快过去一半了,研一马上就要成为过去式了,我打算抓住研一的尾巴,好好梳理一下数据结构与算法,毕竟这些基础知识是很重要的嘛。所以准备在这里搞一个系列的文章,...

MageekChiu ⋅ 2017/06/17 ⋅ 0

二叉排序树的java实现

二叉排序树,又称为二叉查找树。它或者是一棵空树。或者具有以下性质 (1)若它的左子树不空,则左子树所有的结点的值均小于它的根结构的值。 (2)若它在右子树不空,则右子树上所有结点的值...

liuzhangheng ⋅ 2014/04/28 ⋅ 0

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是具有一下特性的二叉树: 若它...

google19890102 ⋅ 04/09 ⋅ 0

二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载 ⋅ 2017/10/19 ⋅ 0

Java Binary Search Tree

Java实现二叉查找树(Binary Search Tree) 对数:(底数β的值一定不能是1或0) 数x(对于底数β)的对数通常写为: 最常用做底数的是e、10和2 如果底数是10,简写成 lg,如果底数是e,简写...

秋风醉了 ⋅ 2015/06/30 ⋅ 0

数据结构与算法 二叉树

最近重新回顾了数据结构中的树,树是一种非线性数据结构,其概念也不少。大家在初次接触树的时候,可能觉得它很难;之所产生这种感觉主要是由于树有一大堆陌生的概念、性质等内容。而当我真正...

云时之间 ⋅ 2017/12/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 21分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 33分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 今天 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部