1. 代码段小站首页
  2. 算法

leetcode98-验证二叉搜索树

彭晨涛 • • 算法 • 阅读 9

原题

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

解法

思想

递归，要考虑整个左子树的最大值小于根节点，整个右子树的最小值大于根节点。通过传参来获取这些信息。

代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        return recursion(root, null, null);
    }

    private boolean recursion(TreeNode root, Integer up, Integer low) {
        if (root == null) {
            return true;
        }
        if (up != null && root.val >= up) {
            return false;
        }
        if (low != null && root.val <= low) {
            return false;
        }
        return recursion(root.left, root.val, low) && recursion(root.right, up, root.val);
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode98-%e9%aa%8c%e8%af%81%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月15日 02:29
下一篇 2020年1月15日 19:54

相关推荐

  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示...

    彭晨涛 彭晨涛
    算法 2019年12月29日
    050

  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3...

    彭晨涛 彭晨涛
    算法 2020年5月11日
    0120

  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例： 输入: [1,2,3,null,5,null,4] 输出:&nb...

    彭晨涛 彭晨涛
    算法 2020年4月22日
    070
  • 海量数据去重-由BitMap引出的布隆过滤器 算法

    海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源： 那些惊艳的算法们（一）——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天...

    彭晨涛 彭晨涛
    2020年2月28日
    01.1K0

  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能...

    彭晨涛 彭晨涛
    算法 2019年12月20日
    080

  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...

    彭晨涛 彭晨涛
    算法 2020年3月21日
    0170

  • leetcode278-第一个错误的版本

    原题 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假...

    彭晨涛 彭晨涛
    算法 2020年1月2日
    070

  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车...

    彭晨涛 彭晨涛
    算法 2020年5月6日
    0100

  • 数组元素左右两边最近较小元素

    原题（来源牛客网） 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例： 输入: ar...

    彭晨涛 彭晨涛
    算法 2020年4月26日
    0640
  • leetcode590-N叉树的后序遍历 算法

    leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树，返回其节点值的后序遍历。 例如，给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单，你可以使用迭代法完成此题吗? ...

    彭晨涛 彭晨涛
    2020年1月20日
    060

发表回复

登录后才能评论