LeetCode 98. 验证二叉搜索树（BST）——递归区间法彻底讲透

LeetCode 98. 验证二叉搜索树BST——递归区间法彻底讲透一、题目描述给定一个二叉树的根节点root判断它是否是一棵合法的二叉搜索树BST。示例输入 2 / \ 1 3 输出True输入 5 / \ 1 4 / \ 3 6 输出False二、什么是二叉搜索树BST二叉搜索树满足左子树所有节点的值都小于当前节点右子树所有节点的值都大于当前节点左右子树本身也必须是二叉搜索树。注意很多同学会误以为node.left.valnode.val node.right.valnode.val就足够了。实际上这是错误的。例如5 / \ 1 6 / \ 3 7节点 3小于 6满足父子关系但是它位于节点 5 的右子树中却小于 5。因此整棵树不是 BST。三、核心思路递归维护取值范围对于每一个节点都维护一个合法区间(low, high)当前节点必须满足lownode.valhigh否则直接返回 False。左子树左子树所有节点 当前节点因此highnode.val右子树右子树所有节点 当前节点因此lownode.val四、递归过程图解例如5 / \ 3 7 / \ 2 4根节点5 ∈ (-∞,∞)左节点3 ∈ (-∞,5)节点 22 ∈ (-∞,3)节点 44 ∈ (3,5)右节点7 ∈ (5,∞)所有节点均满足约束因此是合法 BST。五、完整代码classSolution:defisValidBST(self,root:Optional[TreeNode])-bool:defhelper(node,lowfloat(-inf),highfloat(inf)):# 空节点天然合法ifnotnode:returnTrue# 当前节点必须落在合法区间内ifnot(lownode.valhigh):returnFalse# 检查左子树left_okhelper(node.left,low,node.val)# 检查右子树right_okhelper(node.right,node.val,high)returnleft_okandright_okreturnhelper(root)六、复杂度分析时间复杂度O(n)每个节点访问一次。空间复杂度O(h)h 为树高。平衡树O(logn)极端情况O(n)七、高频易错点1、只比较父节点node.left.valnode.val node.right.valnode.val忽略了祖先节点的约束。2、允许相等BST 必须满足不能写成3、忘记传递区间helper(node.left)helper(node.right)会导致错误答案。八、一句话总结验证 BST 的本质就是检查每个节点是否始终落在祖先节点规定的合法区间内。