原题链接:http://oj.leetcode.com/problems/validate-binary-search-tree/这道题是检查一颗二分查找树是否合法,二分查找树是非常常见的一种数据结构,因为它可以在O(logn)时间内实现搜索。这里我们介绍两种方法来解决这个问题。第一种是利用二分查找树的性质,就是它的中序遍历结果是按顺序递增的。根据这一点我们只需要中序遍历这棵树,然后保存前驱结点,每次检测是否满足递增关系即可。注意以下代码我么用一个一个变量的数组去保存前驱结点,原因是java没有传引用的概念,如果传入一个变量,它是按值传递的,所以是一个备份的变量,改变它的值并不能影响它在函数外部的值,算是java中的一个小细节。代码如下:public boolean isValidBST(TreeNode root) {
ArrayList<Integer> pre = new ArrayList<Integer>();
pre.add(null);
return helper(root, pre);
}
private boolean helper(TreeNode root, ArrayList<Integer> pre)
{
if(root == null)
return true;
boolean left = helper(root.left,pre);
if(pre.get(0)!=null && root.val<=pre.get(0))
return false;
pre.set(0,root.val);
return left && helper(root.right,pre);
}
第二种方法是根据题目中的定义来实现,其实就是对于每个结点保存左右界,也就是保证结点满足它的左子树的每个结点比当前结点值小,右子树的每个结点比当前结点值大。对于根节点不用定位界,所以是无穷小到无穷大,接下来当我们往左边走时,上界就变成当前结点的值,下界不变,而往右边走时,下界则变成当前结点值,上界不变。如果在递归中遇到结点值超越了自己的上下界,则返回false,否则返回左右子树的结果。代码如下:public boolean isValidBST(TreeNode root) {
return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
boolean helper(TreeNode root, int min, int max)
{
if(root == null)
return true;
if(root.val <= min || root.val >= max)
return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
上述两种方法本质上都是做一次树的遍历,所以时间复杂度是O(n),空间复杂度是O(logn)。个人其实更喜欢第一种做法,因为思路简单,而且不需要用到整数最大值和最小值这种跟语言相关的量来定义无穷大和无穷小。二分查找树在面试中非常常见,因为它既是树的数据结构,又带有一些特殊的性质,并且模型简单,很适合在面试中对基本的数据结构和算法进行考核,还是尽量要对二分查找树理解比较透彻哈。
分享到:
相关推荐
作者: 负雪明烛个人博客: :
Validate Binary Search Tree - Java Recursive - Java Iterative - Java Inorder 0099 Recover Binary Search Tree - Java Recursive 0101 Symmetric tree - Java Recursive - Java Iterative - C Recursive...
leetcode ...Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ
validate-npm-package-name, 给定字符串是否可以接受的npm包名称? validate-npm-package-name给我一个字符串,我告诉你它是否是有效的npm 包名称。这个软件包导出一个带有 string 作为输入并返回具有两个属性的对象...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
验证Git提交消息 根据各种预设验证提交消息安装yarn add validate-git-commit-msg -D特征即使还有其他一些程序包也可以执行此操作,但该程序包的生活质量却发生了一些变化。 让您决定如何验证提交消息(请参阅) 它...
$ validate-commit-msg创建到./lib/validate-commit-msg.js的符号链接.git/hooks/commit-msg ,该链接在每次提交时执行。 钩子脚本根据在每次提交时验证提交消息。 安装 $ npm install validate-commit-message ...
官方离线安装包,亲测可用
借助此简单扩展,您可以将自己的验证添加到任何字段,例如“ validate-number”,“ validate-email”,“ validate-xxx validate-yyy validate-zzz”。 用法 安装模块 像往常一样创建小部件 在节点的widget.xml中...
html-validate-webpack-plugin 用于webpack的插件关于插件此插件是围绕 cli的简单包装,可在每次Webpack编译后自动进行验证。安装npm install html-validate-webpack-plugin --save-dev 注意:安装html-validate并...
validate-npm-package-license 给我一个字符串,我会告诉您它是否是有效的npm软件包许可证字符串。 var valid = require ( 'validate-npm-package-license' ) ; SPDX许可证标识符是有效的许可证字符串: var ...
资源来自pypi官网。 资源全名:validate-bes-xml-1.1.1.tar.gz
本资源是jquery validation插件的相关文件,包括了四个文件:jquery-1.6.4.js ,jquery.metadata.js ,jquery.validate.js ,jquery.validate.messages_cn.js
离线安装包,亲测可用
主要介绍了jQuery Validate 无法验证 chosen-select元素的解决方法,需要的朋友可以参考下
资源分类:Python库 所属语言:Python 资源全名:ss_validate-0.3.3-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
安装$ npm install validate.io-binary-string 要在浏览器中使用,请使用 。用法 var isBinaryString = require ( 'validate.io-binary-string' ) ;isBinaryString( 值 ) 验证value是否为二进制string ; 即, 1和0...
验证原始协议(PGV) ...import "validate/validate.proto" ; message Person { uint64 id = 1 [(validate.rules) .uint64.gt = 999 ]; string email = 2 [(validate.rules) .string.email = true ]; string n
开源项目-lyft-protoc-gen-validate.zip,用于生成polyglot消息验证器的Protoc插件