专栏首页爱写BugLeetCode 29:验证二叉搜索树 Validate Binary Search Tree

LeetCode 29:验证二叉搜索树 Validate Binary Search Tree

题目:

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

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.

示例 1:

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

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。

解题思路:

刚看的时候以为只要满足任一结点值均大于左子结点,小于右子结点就是二叉搜索树:

node.left.val < node.val < node.right.val

实际上还有一个条件:每个结点的值应当大于其左子树任一结点值,小于其右子树任意结点值。如下二叉树:

    5
   / \
  1   7
     / \
    4   6

该二叉树其中任一结点值均大于左子结点,小于右子结点,但并非二叉搜索树,因为结点 4 小于结点 5。

实际上只要记录结点值与上界和下界,满足 lower < node.val < upper,代码很简单如下:

Java

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

    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null)
            return true;

        int val = node.val;
        if (lower != null && val <= lower)
            return false;
        if (upper != null && val >= upper)
            return false;

        if (!helper(node.left, lower, val))
            return false;
        if (!helper(node.right, val, upper))
            return false;

        return true;
    }
}

Python

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(node, lower = float('-inf'), upper = float('inf')):
            if not node:
                return True

            val = node.val
            if val <= lower or val >= upper:
                return False

            if not helper(node.left, lower, val):
                return False
            if not helper(node.right, val, upper):
                return False
            return True

        return helper(root)

Golang

const lower = math.MinInt64
const upper = math.MaxInt64

func isValidBST(root *TreeNode) bool {
    return helper(root, lower, upper)
}

func helper(node *TreeNode, lower, upper int) bool {
    if node == nil {
        return true
    }
    val := node.Val
    if lower >= val || upper <= val {
        return false
    }
    if !helper(node.Left, lower, val) {
        return false
    }
    if !helper(node.Right, val, upper) {
        return false
    }
    return true
}

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 14:Longest Common Prefix 最长公共前缀

    Write a function to find the longest common prefix string amongst an array of st...

    爱写bug
  • Leetcode 54:Spiral Matrix 螺旋矩阵

    Given a matrix of m x n elements (m rows, n columns), return all elements of the...

    爱写bug
  • leetcode ​# 54:Spiral Matrix 螺旋矩阵

    Given a matrix of m x n elements (m rows, n columns), return all elements of the...

    爱写bug
  • NFS介绍,NFS服务端安装配置,NFS配置选项

    NFS(Network File System)即网络文件系统,是FreeBSD支持的文件系统中的一种,它允许网络中的计算机之间通过TCP/IP网络共享资源。在...

    端碗吹水
  • 【leetcode】八皇后

    JNingWei
  • 内嵌IE网页窗口中消除IE默认脚本设置影响的方法

            随着人们对客户端软件界面要求的不断提高,软件开发商面临着一个问题:如何快速廉价开发出各种丰富效果的UI界面。设计出一套丰富控件的界面库是不容易的...

    方亮
  • AI系统DeepRay实时处理视频,重建模糊的镜头帧

    雨,烟雾,污垢等往往会干扰到摄影师,导致拍摄的景象失真。研发公司Cambridge Consultants的研究人员表示,他们利用AI可以实时重建镜头中受损或模...

    AiTechYun
  • 【Python】记录程序运行时间

    后端技术漫谈
  • 肥皂与手纸:神奇的电商大数据分析

    11.11光棍节已经过去,12.12促销又要到来,回望双十一的疯狂与激情,哪些人在买小米、哪些人在买华为,哪些人在买林志玲,哪些人在买杜蕾斯,都将是有趣的话题。...

    CDA数据分析师
  • 天蝎座性福指数最低-肥皂与手纸:神奇的电商大数据分析

    PPV课大数据 电商行业的人一定对啤酒与尿布的故事有所耳闻,20世纪90年代美国沃尔玛超市管理人员分析销售数据时候,发现了一个奇怪的现象:在一些情况下,啤酒和尿...

    小莹莹

扫码关注云+社区

领取腾讯云代金券