当前位置:   article > 正文

Python编程 | 验证二叉搜索树_python验证二叉树是否是二叉搜索树

python验证二叉树是否是二叉搜索树


验证二叉搜索树

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<=2311

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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

3,运行结果

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/223007
推荐阅读
相关标签
  

闽ICP备14008679号