力扣刷题#33-0098-验证二叉搜索树
题目
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。
有效 BST 定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
输入: root = [2,1,3]2/ \1 3
输出: true
输入: root = [5,1,4,null,null,3,6]5/ \1 4/ \3 6
输出: false
解释: 根节点 5 大于 4 和 6，但 3 在右子树里却小于 5
我的思路之旅：从"写不出代码"到"通了"
第一版：只比较父子节点（错）
我最初的想法是：每个节点检查"左孩子 < 我 < 右孩子"。但这是不够的：
5/ \4 6/ \3 7
每个节点和直接孩子都满足"左小右大"：4<5 ✓、6>5 ✓、3<6 ✓、7>6 ✓——但它不是合法 BST。因为 3 虽然比 6 小，却比根节点 5 还小。
教训：光比较 root 和它的孩子不够，必须验证"整棵左子树都比 root 小、整棵右子树都比 root 大"。
顿悟：传"边界"往下压
每个节点能取的值范围被祖先们限制住了：
5 ← 范围 (-∞, +∞)/ \4 6 ← 左子树 (-∞,5)；右子树 (5,+∞)/ \3 7 ← 3 的范围应是 (5,6)，但 3 < 5 → 违规！
关键：递归时带上 min 和 max 边界参数，一路往下压：
dfs(node, 下限, 上限)：节点值必须在 (下限, 上限) 开区间内左孩子：上限收紧为 node->val右孩子：下限抬高为 node->val
我的 AC 代码（含注释）
class Solution {
public:// 验证以 node 为根的子树是否合法，且所有节点值必须在 (min, max) 开区间内bool dfs(TreeNode* root, long long min, long long max) {// ① 空节点：没有元素，天然合法if (root == nullptr) return true;// ② 当前节点值超出边界 → 违规// 用 <= 和 >=：BST 要求严格小/严格大，相等的值也不允许if (root->val >= max || root->val <= min) return false;// ③ 递归验证左右子树，边界更新：// 左子树的所有值必须小于 root->val（上限收紧）// 右子树的所有值必须大于 root->val（下限抬高）return dfs(root->left, min, root->val)&& dfs(root->right, root->val, max);}bool isValidBST(TreeNode* root) {// 根节点没有上下限限制，用无穷大/无穷小兜底// 用 long long 避免 int 边界值（INT_MIN/INT_MAX）的坑return dfs(root, LLONG_MIN, LLONG_MAX);}
};
代码逐段解析
第 4 行：函数签名
bool dfs(TreeNode* root, long long min, long long max)
三个参数：当前节点 + 允许范围的下限 + 上限。min/max 用 long long 而不是 int——因为测试用例可能包含 INT_MIN/INT_MAX，用 int 边界会误判。
第 5-6 行：空节点
if (root == nullptr) return true;
空树没有元素，不违反任何规则，返回 true。
第 7-8 行：越界判断
if (root->val >= max || root->val <= min) return false;
当前值必须严格在 (min, max) 内。用 >= 和 <= 而不是 > 和 <——BST 不允许相等值（题目说"小于/大于"，不是"小于等于/大于等于"）。
第 9-11 行：递归验证
return dfs(root->left, min, root->val)&& dfs(root->right, root->val, max);
| 递归调用 | 边界变化 | 含义 |
|---|---|---|
dfs(left, min, root->val) |
上限收紧为 root->val |
左子树所有节点必须 < root->val |
dfs(right, root->val, max) |
下限抬高为 root->val |
右子树所有节点必须 > root->val |
&&：左右都必须合法。左边不合法立即短路返回 false。
第 14-15 行：主函数
return dfs(root, LLONG_MIN, LLONG_MAX);
根节点的范围是 (-∞, +∞)，用 LLONG_MIN/LLONG_MAX 表示（#include <climits>）。这是解决"只看父子不够"的关键——边界从根一路传递，所有祖先的约束都会被带到每个节点。
为什么"传边界"能解决第一版的漏洞？
以 [5,1,4,null,null,3,6] 为例：
dfs(5, -∞, +∞) 5 在范围内 ✓dfs(1, -∞, 5) 1 在范围内 ✓dfs(4, 5, +∞) 4 不在 (5,+∞) → return false！← 第一版漏掉的
4 进入右子树时，它的下限被祖先 5 抬高成了 5。4 < 5 → 违规被抓住。
而第一版只比较 4 和它的孩子（3、6）——3 和 6 都满足局部关系，但 3 相对 5 是违规的。边界传递把"远亲约束"也带到了每个节点。
复杂度分析
| 维度 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(h) | 递归栈深度 = 树高 |
关键点总结
| 关键点 | 说明 |
|---|---|
| 第一版错误 | 只比较父子节点 → 漏掉"远亲越界" |
| 核心思想 | 边界传递：每个节点携带 (min, max) 区间 |
| 边界更新 | 左子收紧上限，右子抬高下限 |
| 严格性 | 用 <=/>= 判违规，BST 不允许相等 |
| long long | 避免 INT_MIN/INT_MAX 边界值误判 |
本文档由 AI 辅助生成，作者提供问题，思路和代码，AI仅负责文本修饰，综合获得以上内容。