赞
踩
# -*- 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
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。