Python编程 | 验证二叉搜索树

Python编程 | 验证二叉搜索树

文章目录

验证二叉搜索树

1，程序简介

有效 二叉搜索树定义如下：

示例 1：示例 2：提示： 2，程序代码3，运行结果

---

验证二叉搜索树 1，程序简介

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下：

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

输入：root = [2,1,3]输出：true 示例 2：

输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。 提示：

树 中 节 点 数 目 范 围 在 [ 1 , 1 0 4 ] 内 树中节点数目范围在[1, 10^4] 内 树中节点数目范围在[1,104]内 − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^{31} <= Node.val <= 2^{31} - 1 −231<=Node.val<=231−1 2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Sat Jan  8 08:22:04 2022
Function: 验证二叉搜索树
@author: 小梁aixj
"""
import sys
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class List2Tree(object):
    def __init__(self, nums: list):
        self.nums = nums
        self.queue = []
        if len(nums) == 1:
            self.root = TreeNode(self.nums.pop(0))
        else:
            a = self.nums.pop(0)
            b = self.nums.pop(0)
            c = self.nums.pop(0)
            self.root = TreeNode(a)
            if b is not None:
                self.root.left = TreeNode(b)
            else:
                self.root.left = b
            if c is not None:
                self.root.right = TreeNode(c)
            else:
                self.root.right = c
            self.queue.append(self.root.left)
            self.queue.append(self.root.right)
    def convert(self):
        while len(self.nums) > 0 and len(self.queue)> 0:
            node = self.queue.pop(0)
            if node is not None:
                num= self.nums.pop(0)
                if num is not None:
                    node.left = TreeNode(num)
                else:
                    node.left = num
                if len(self.nums) > 0:
                    num = self.nums.pop(0)
                else:
                    num = None
                if num is not None:
                    node.right = TreeNode(num)
                else:
                    node.right = num
                self.queue.append(node.left)
                self.queue.append(node.right)
        return self.root
class Solution(object):
    def isValidBST(self, root):
        root = List2Tree(root).convert()
        return self.isVaild_helper(root, -sys.maxsize - 1, sys.maxsize)
    def isVaild_helper(self, root, minVal, maxVal):
        if root is None:
            return True
        if root.val >= maxVal or root.val <= minVal:
            return False
        return self.isVaild_helper(root.left, minVal, root.val) and self.isVaild_helper(root.right, root.val, maxVal)
# %%
s = Solution()
print(s.isValidBST([5,1,4,None,None,3,6]))#false
print(s.isValidBST([2,1,3]))#true

3，运行结果