文档章节

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

一贱书生
 一贱书生
发布于 2016/11/18 11:01
字数 183
阅读 5
收藏 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
博文 724
码字总数 600123
作品 0
检查是否为BST(二叉查找树(或二叉排序树、二叉搜索树))

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

笨拙的小Q
2016/04/20
15
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
判断一棵二叉树是否为搜索二叉树和完全二叉树

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

junjunba2689
04/19
0
0
数据结构——二叉树、二叉查找树

参考:Mark Allen Weiss 著《数据结构与算法分析——C语言描述》(第二版) 主要内容:二叉树及二叉查找树 一、二叉树 1 二叉树定义   二叉树是一棵每个节点都不能有多于两个儿子的树 2 实...

翠竹09
08/13
0
0
数据结构分析之二叉树

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

wustor
2017/11/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Coding and Paper Letter(二十四)

资源整理。这一次内容有点多,拆为两篇,这一篇主要针对Coding。 Coding: 1.R语言包geex,用于估计参数的框架和来自R中的一组无偏估计方程(即M-估计)的经验夹层协方差矩阵。 geex 2.R语言...

胖胖雕
22分钟前
1
0
Python中使用SQLite

SQLite: SQLite是一种数据库,Python中集成了SQLite3,所以在Python中使用SQLite,可以直接导入SQLite包,不需要做额外的配置。 更多的SQLite简介和相关知识可以查看专门的教程:http://ww...

akane_oimo
24分钟前
1
0
05《Java核心技术36讲》之几种字符串类有什么区别?

一、提出问题 今天,我们来聊聊日常使用的字符串,别看它似乎很简单,但其实字符串几乎在所有编程语言里都是个特殊的存在,因为不管是数量还是体积,字符串都是大多数应用中的重要组成。 今天...

飞鱼说编程
42分钟前
1
0
Univalsal_ImageLoader源码结构与创建者模式 初步小结

最近在回归看Univalsal_ImageLoader源码,本想自己也实现试试写一个,看源码是为了学习看能否使用,助于自己可以写出有自己逻辑结构的代码。 首先我们初始化ImageLoader的配置初始化的时候,...

DannyCoder
今天
0
0
计算卷积神经网络浮点数运算量

前言 本文主要是介绍了,给定一个卷积神经网络的配置之后,如何大概估算它的浮点数运算量。 相关代码:CalFlops,基于MXNet框架的 Scala 接口实现的一个计算MXNet网络模型运算量的demo。 正文...

Ldpe2G
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部