验证二叉搜索树
Validate Binary Search Tree
本机进度仅保存在当前浏览器
题目描述
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。有效 BST 定义：左子树所有节点值严格小于根，右子树所有节点值严格大于根，左右子树也必须是 BST。
示例：[2, 1, 3] 有效；[5, 1, 4, null, null, 3, 6] 无效（4 大于根 5 却在右子树内违反约束）。
解题思路
- 常见错误是只比较节点与直接孩子；正确做法是把祖先的约束向下传递——每个节点有取值上下界 (low, high)。
- 递归检查当前值落在开区间 (low, high) 内，再以 (low, val) 检查左子树、(val, high) 检查右子树。
- 另一种等价思路：BST 的中序遍历严格递增，中序扫描时比较当前值与前一个值即可。
参考实现
查看参考实现Python · 建议先自行作答
def isValidBST(root):
def check(node, low, high):
if not node:
return True
if not low < node.val < high:
return False
# 左子树上界收缩为当前值，右子树下界抬升为当前值
return check(node.left, low, node.val) and check(node.right, node.val, high)
return check(root, float('-inf'), float('inf'))