LeetCode | 面试题 04.05. 合法二叉搜索树【Python】

港控/mmm° 2022-11-08 14:15 137阅读 0赞

## 问题 ##

[力扣][Link 1]

实现一个函数，检查一棵二叉树是否为二叉搜索树。

**示例 1:**

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

**示例 2:**

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

## 思路 ##

**递归**

二叉搜索树：根节点值大于左子树节点最大值，小于右子树节点最小值。
    左右子树也要满足二叉搜索树性质。

## 代码 ##

### Python3 ###

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def isValidBST(self, root: TreeNode) -> bool:
            return self.isValid(root, None, None)
    
        # 辅助函数
        def isValid(self, root: TreeNode, min_: TreeNode, max_: TreeNode):
            if not root:
                return True
            if min_ != None and root.val <= min_.val:
                return False
            if max_ != None and root.val >= max_.val:
                return False
            return self.isValid(root.left, min_, root) and self.isValid(root.right, root, max_)

## 链接 ##

[GitHub][]

[Link 1]: https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/Interview-04.05-Legal-Binary-Search-Tree-LCCI

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关面试热题（验证二叉搜索树）

> 给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。 > > 有效二叉搜索树定义如下： > > 节点的左子树只包含小于当前节点的数。

ゞ浴缸里的玫瑰/ 2023年10月14日 18:59/ 0 赞/ 8 阅读

相关 LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST

向右看齐/ 2023年10月06日 22:23/ 0 赞/ 19 阅读

相关 Leetcode 面试题 04.05. 合法二叉搜索树

Leetcode 面试题 04.05. 合法二叉搜索树 1、问题分析 2、问题解决 3、总结 1、问题分析本质上就是一个二叉树的遍历问题，

爱被打了一巴掌/ 2023年03月14日 08:03/ 0 赞/ 4 阅读

相关快乐的LeetCode --- 面试题 04.05. 合法二叉搜索树

题目描述：实现一个函数，检查一棵二叉树是否为二叉搜索树。示例 1: 输入: 2 / \ 1 3 输出:

ゝ一纸荒年。/ 2023年02月20日 02:14/ 0 赞/ 10 阅读

相关 LeetCode | 面试题 04.05. 合法二叉搜索树【Python】

问题 [力扣][Link 1] 实现一个函数，检查一棵二叉树是否为二叉搜索树。示例 1: 输入: 2 / \ 1

港控/mmm°/ 2022年11月08日 14:15/ 0 赞/ 138 阅读

相关 LeetCode | 0669. 修剪二叉搜索树【Python】

问题 [力扣][Link 1] 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, h

雨点打透心脏的1/2处/ 2022年11月03日 10:37/ 0 赞/ 159 阅读

相关程序员面试金典-0405-合法二叉搜索树

程序员面试金典-0405-合法二叉搜索树思路：1. 通过二叉搜索树中序遍历 2. 遍历中序遍历的结果，如果是有序的话，则为合法二叉搜索树实现一个函数，检

曾经终败给现在/ 2022年10月19日 12:39/ 0 赞/ 145 阅读

相关 leetcode 700. 二叉搜索树中的搜索(python)

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。例如，给定

左手的ㄟ右手/ 2022年05月15日 14:04/ 0 赞/ 231 阅读

相关【面试题精选】二叉搜索树详解

一、二叉搜索树的概念及特点二叉搜索树（BLT）：Binary Search Tree，又名二叉排序树，二叉查找树，是一种常见的二叉树类型。它是一棵空树或具有以下特点的二

r囧r小猫/ 2022年03月07日 00:54/ 0 赞/ 248 阅读

相关 leetcode 98题 .验证二叉搜索树

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征a：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前...

小灰灰/ 2021年01月10日 15:40/ 0 赞/ 656 阅读