知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 验证二叉搜索树 ## 题目(LeetCode 98) 判断一棵二叉树是否是有效的二叉搜索树(BST)。 BST 的定义: - 左子树所有节点的值 < 根节点的值 - 右子树所有节点的值 > 根节点的值 - 左右子树也分别是 BST ``` 有效 BST ✓ 无效 BST ✗ 2 5 / \ / \ 1 3 1 4 / \ 3 6 ↑ 3 < 5,但 3 在 5 的右子树里,不合法 ``` ## 大白话理解 ### 常见错误思路 很多人第一反应是:每个节点只要比左孩子大、比右孩子小就行了。 ``` 5 / \ 1 6 / \ 3 7 节点 6:左孩子 3 < 6 ✓,右孩子 7 > 6 ✓ 但是!3 在 5 的右子树里,3 < 5,违反了 BST 的定义 ``` 错在哪?只比较了父子关系,没有考虑祖先的约束。 ### 正确思路:每个节点都有一个合法的取值范围 ``` 5 范围:(-∞, +∞) / \ 1 6 1 的范围:(-∞, 5) 6 的范围:(5, +∞) / \ 3 7 3 的范围:(5, 6) ← 3 不在这个范围内,不合法! 7 的范围:(6, +∞) ``` 往左走,上界变成当前节点的值。 往右走,下界变成当前节点的值。 ## 解法一:递归传递上下界 ```java public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node == null) return true; // 当前节点必须在 (min, max) 范围内 if (node.val <= min || node.val >= max) return false; // 左子树的上界是当前节点值,右子树的下界是当前节点值 return validate(node.left, min, node.val) && validate(node.right, node.val, max); } ``` ### 逐行拆解 ``` validate(node, min, max) 的含义: node 这棵子树的所有节点值是否都在 (min, max) 范围内 初始调用:validate(root, -∞, +∞) → 根节点没有限制 往左走:validate(left, min, node.val) 左子树的所有值必须 < 当前节点值 所以上界变成 node.val 往右走:validate(right, node.val, max) 右子树的所有值必须 > 当前节点值 所以下界变成 node.val ``` ## 解法二:中序遍历递增 BST 的中序遍历结果一定是严格递增的。所以中序遍历一遍,检查是否递增就行。 ``` 2 / \ 1 3 中序遍历:1, 2, 3 → 严格递增 ✓ 5 / \ 1 6 / \ 3 7 中序遍历:1, 5, 3, 6, 7 → 5 > 3,不递增 ✗ ``` ```java class Solution { private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) return true; // 中序:先检查左子树 if (!isValidBST(root.left)) return false; // 检查当前节点是否大于前一个值 if (root.val <= prev) return false; prev = root.val; // 再检查右子树 return isValidBST(root.right); } } ``` 这个方法更直观:中序遍历就是"左→根→右",BST 的中序遍历一定是递增的,所以每个节点只要比前一个大就行。 ## 画图模拟(解法一) ``` 5 / \ 1 6 / \ 3 7 validate(5, -∞, +∞) → 5 在范围内 ✓ validate(1, -∞, 5) → 1 在范围内 ✓ validate(null) → true validate(null) → true validate(6, 5, +∞) → 6 在范围内 ✓ validate(3, 5, 6) → 3 不在 (5,6) 范围内 ✗ → 返回 false 结果:false ✓ ``` ## 复杂度 - 时间:O(n) - 空间:O(h) ## 一句话总结 每个节点都有一个合法范围,往左走收紧上界,往右走收紧下界。或者直接中序遍历检查递增。 --- 上一篇:[05 - 二叉树的直径](./05-diameter.md) | 下一篇:[07 - 最近公共祖先](./07-lowest-common-ancestor.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入