专栏首页爱写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 条评论
登录 后参与评论

相关文章

  • LeetCode98题 验证二叉搜索树(Validate Binary Search Tree)

    https://leetcode-cn.com/problems/validate-binary-search-tree/

    code随笔
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • Python3刷题系列(四)

    https://leetcode.com/problems/happy-number/

    用户5473628
  • ​LeetCode刷题实战98:验证二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode - 二叉搜索树中的插入操作

    原题地址:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

    晓痴
  • 资源 | 从算法到数据结构,百道面试问题实现答案集合

    选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

    机器之心
  • LeetCode 173. Binary Search Tree Iterator(搜索二叉树)

    题解:题目说Next()的时间效率O(1),空间效率O(h),h为树的高度。我们维护一个栈,把前序遍历的左子树的结果存进去。

    ShenduCC
  • 二叉树问题(一)-LeetCode 110、617、101、814、655、98、654(递归思路)

    给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

    算法工程师之路
  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • DFS基础问题-LeetCode 98、101(二叉树中序遍历,层次遍历)

    假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

    算法工程师之路
  • 【leetcode刷题】T154-二叉搜索树中的插入操作

    https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

    木又AI帮
  • ​LeetCode刷题实战99:恢复二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 【leetcode刷题】20T50-验证二叉搜索树

    https://leetcode-cn.com/problems/validate-binary-search-tree

    木又AI帮
  • LeetCode - 二叉搜索树中的搜索

    原题地址:https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

    晓痴
  • [Leetcode][二叉树]相关题目汇总/分析/总结

    前中后三种序列,递归都是一样的理解。迭代的话,前后两个可以互相理解。中序需要单独理解。当然我认为可能我还没有理解透彻。

    蛮三刀酱
  • 【leetcode刷题】T141-把二叉搜索树转化成更大的树

    https://leetcode-cncom/problems/convert-bst-to-greater-tree/

    木又AI帮
  • 二叉树高频题

    Given a binary tree, return the preorder traversal of its nodes' values.

    王脸小
  • ​LeetCode刷题实战449:序列化和反序列化二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 二叉树-LeetCode 235、236、226、230(中序,LCA,DFS)

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 ...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券