LeetCode 98. 验证二叉搜索树
📌 题目描述
题目级别：中等
给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含严格小于当前节点的数。
- 节点的右子树只包含严格大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
💡 破题思路：区间约束法 (自顶向下)
验证 BST 的最大陷阱是：不能只判断当前节点和它的左右孩子。
比如[5,4,6,null,null,3,7]，节点6的左孩子是3，虽然3 < 6局部成立，但3身处根节点5的右子树中，它必须大于5！
因此，我们需要自顶向下地传递一个合法区间(min, max)：
- 根节点的区间是
(-∞, +∞)。 - 往左子树走时，当前节点的值就成了左子树的上限。
- 往右子树走时，当前节点的值就成了右子树的下限。
高光技巧（指针代替数值）：
很多解法用LONG_MIN来初始化极小值，但如果节点值本身就是long long类型的下界呢？
最优的写法是使用TreeNode*指针来表示边界。如果指针为空，表示没有边界限制；如果指针有值，直接解引用比较。优雅且绝对不会溢出。
💻 C++ 代码实现 (指针边界版)
classSolution{public:boolisValidBST(TreeNode*root){// 初始状态：上下界均无限制 (nullptr)returndfs(root,nullptr,nullptr);}booldfs(TreeNode*root,TreeNode*minN,TreeNode*maxN){// 走到空节点，说明没有违反规则if(!root)returntrue;// 如果下界存在，且当前值没有严格大于下界，判负// 如果上界存在，且当前值没有严格小于上界，判负if((minN&&root->val<=minN->val)||(maxN&&root->val>=maxN->val))returnfalse;// 向左子树递归：下界不变，上界更新为当前节点// 向右子树递归：下界更新为当前节点，上界不变returndfs(root->left,minN,root)&&dfs(root->right,root,maxN);}};
