Hot-98 验证二叉搜索树

1、解法1递归返回时向上返回子树的最大值和最小值# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def isValidBST(self, root: Optional[TreeNode]) - bool: # 递归判断 self.flag True # 不对需要一路记录祖先节点中的最大值和最小值而且需要递归的时候向上返回 def dfs(Node): if not Node: return None,None if Node.left: left_max,left_min dfs(Node.left) # 返回左子树中的最大值和最小值 # 先和当前节点的val与max做判断 if left_max ! None and left_max Node.val: self.flag False # 更新并且返回上一层 left_Node_max max(left_max,Node.val) left_Node_min min(left_min,Node.val) if Node.right: right_max,right_min dfs(Node.right) if right_min ! None and right_min Node.val: self.flag False right_Node_max max(right_max,Node.val) right_Node_min min(right_min,Node.val) if Node.leftNone and Node.rightNone: return Node.val,Node.val elif Node.left!None and Node.rightNone: return left_Node_max,left_Node_min elif Node.leftNone and Node.right!None: return right_Node_max,right_Node_min else: return max(left_Node_max,right_Node_max),min(left_Node_min,right_Node_min) dfs(root) return self.flag2、解法2如果能够设置inf和-inf的话也可以自顶向下from typing import Optional class Solution: def isValidBST(self, root: Optional[TreeNode]) - bool: def dfs(node, lower, upper): if not node: return True # 当前节点的值必须在 (lower, upper) 范围内 if node.val lower or node.val upper: return False # 左子树上限变为当前节点值 # 右子树下限变为当前节点值 return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper) return dfs(root, float(-inf), float(inf))