LeetCode第[98]题(Java):Validate Binary Search Tree(验证二叉搜索树)

题目:验证二叉搜索树文章地址https://www.yii666.com/article/756104.html网址:yii666.com文章来源地址:https://www.yii666.com/article/756104.html

难度:Medium

题目内容

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

翻译

给定一棵二叉树,确定它是否是一个有效的二叉搜索树(BST)。

BST的定义如下:

节点的左子树只包含小于节点键的键节点。

节点的右子树只包含大于节点键的键节点。

左和右子树都必须是二叉搜索树。

Example 1:网址:yii666.com<

Input:
2
/ \
1 3
Output: true

Example 2:

    5
/ \
1 4
  / \
  3 6
Output: false

我的思路:搜索二叉树的验证就是要求每一个子树都是满足搜索树的“左小右大”的规定,

1、先判断自己作为根节点的左右二叉是否符合;

2、然后返回左右节点的递归结果的 “与” (全都符合才算符合)

我的代码

     public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
} if (root.left != null) {
TreeNode cur = root.left;
while (cur.right != null) {
cur = cur.right;
}
if (cur.val >= root.val) {
return false;
}
} if (root.right != null) {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
if (cur.val <= root.val) {
return false;
}
} return isValidBST(root.left) && isValidBST(root.right);
}

我的复杂度:O(N*logN)

编码过程中的问题

1、没仔细看题,而且记错搜索树的定义了,当出现两个值相等的时候,此时不是搜索树;文章来源地址https://www.yii666.com/article/756104.html

2、最开始只考虑到判断根节点和左右两个子节点就行了,结果后面案例跑错了,例如:

    5
/ \
1 6
  / \
  3 7 每个子树都是正确的二叉搜索树,但是整体上看,5的右子树内有比它小的3,所以此树不是二叉搜索树。

此时想到二叉树删除算法,当删除节点有两个子节点的时候,此时会选择此节点左节点的最右子系节点,或者右节点的最左子系节点进行代替,所以这两个节点值才是最接近根节点值的节点,所以每次的单个子树判断应该判断这两个,而不是左右子节点就行了。

答案代码

     public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
} public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}

答案复杂度:O(N)

答案思路

也是利用了递归的思想,分别对每一个子树进行判断,但是它的亮点在于在判断的时候并不需要对子树进行搜索“最相近的值”,而是利用了“最大值”、“最小值”的思想:

对于每个子树,都有一个最大值和一个最小值,

对于左子树,最大值就是它的根节点的值,最小值是根节点的最小值(左父亲或者MIN_VALUE)

对于右子树,最小值就是它的根节点的值,最大值是根节点的最大值(右父亲或者MAX_VALUE)

例如:

   5
/ \
1 6
  / \
  3 7
5的满足小于最大值,大于最小值,然后递归(1,MIN,5) && 递归(4,5,MAX)
。。。
3节点的最大值为6,最小值应该为5,此时不满足,所以return false 其实还有一种非递归的解法:中序遍历,利用二叉搜索树中序遍历的有序性(在中序遍历的出栈时判断此值是否小于之前出栈的那个节点的值)
 public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}

注意:不能使用出栈值与栈顶进行比较,因为在中序遍历的过程中栈顶可能为空,所以此时无法比较。

 

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

LeetCode第[98]题(Java):Validate Binary Search Tree(验证二叉搜索树)-相关文章

  1. Java [Leetcode 94]Binary Tree Inorder Traversal

  2. Java [Leetcode 144]Binary Tree Preorder Traversal

  3. Java [Leetcode 257]Binary Tree Paths

  4. Java [Leetcode 102]Binary Tree Level Order Traversal

  5. Java [Leetcode 107]Binary Tree Level Order Traversal II

  6. LeetCode第[98]题(Java):Validate Binary Search Tree(验证二叉搜索树)

  7. A multi-faceted language for the Java platform

    最近在研究关于groovy 相关的技术 希望有研究交到研究这方面的朋友Groovy 最新的地址http://www.groovy-lang.org/

  8. java 集合 Se HashTreeSet

    Set接口 Set是Collection的子接口,与List相对 Set集合中的元素的特点是1,无序性 2,无下标3,无重复的元素 Set是个接口,所以无法直接创建对象,要依赖它的实现类来创建对象 Set的实现类有两个,一个是HashSet,另一个是TreeSet输出的结果是Set的成员方法基本上都是继承了collection方法 下

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png