题目
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示： - 树中节点数目范围在[1, 104] 内
- -231 <= Node.val <= 231 – 1
我的代码（Python）
version 1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def checkUpperBound(root: Optional[TreeNode], upperBound: int) -> bool:
if not root:
return True
return root.val < upperBound and checkUpperBound(root.left, root.val) and checkLowerBound(root.right, root.val) and checkUpperBound(root.right, upperBound)
def checkLowerBound(root: Optional[TreeNode], lowerBound: int) -> bool:
if not root:
return True
return root.val > lowerBound and checkUpperBound(root.left, root.val) and checkLowerBound(root.left, lowerBound) and checkLowerBound(root.right, root.val)
return checkUpperBound(root.left, root.val) and checkLowerBound(root.right, root.val)最开始没想到上限下限要同时限制，所以分别定义了函数，调用起来比较繁琐。
version2
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def checkBound(node: Optional[TreeNode], upperBound: Optional[int], lowerBound: Optional[int]) -> bool:
if not node:
return True
return (node.val < upperBound if upperBound is not None else True) and (node.val > lowerBound if lowerBound is not None else True) and checkBound(node.left, node.val, lowerBound) and checkBound(node.right, upperBound, node.val)
return checkBound(root, None, None)上下限一起比较，更方便。
点评
官方解法一和我的第二个版本一样。
容易忽略的就是比较子树时上下限都要考虑。
另外在python中我一开始忽略了一点：if upperBound这种判断方式，如果upperBound是None，这是False没错；但是如果upperBound < 0，这个判断还是False。而我的本意只是判断是否为None，这就造成了错误。
中序遍历的做法很有趣，没想到。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog