资讯详情

力扣刷题#33-0098-验证二叉搜索树

题目

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。

有效 BST 定义如下：

1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 所有左子树和右子树自身必须也是二叉搜索树。

输入: 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仅负责文本修饰，综合获得以上内容。