LeetCode 98：验证二叉搜索树 —— 从局部判断到全局范围约束的递归思想
一、题目描述
给你一个二叉树的根节点root，判断它是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含严格小于当前节点的数。
- 节点的右子树只包含严格大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例：
输入：
root = [2,1,3]输出：
true对应二叉树：
2 / \ 1 3满足：
1 < 2 < 3所以是有效二叉搜索树。
另一个例子：
输入：
root = [5,1,4,null,null,3,6]输出：
false结构：
5 / \ 1 4 / \ 3 6虽然：
3 < 4但是：
4 < 54 出现在 5 的右子树中，不满足：
右子树所有节点 > 根节点所以不是有效 BST。
二、为什么这道题值得学习？
这道题是二叉搜索树判断的经典题，也是面试高频题。
它考察三个核心：
1. 二叉搜索树性质
BST 满足：
左子树节点 < 根节点 < 右子树节点例如：
8 / \ 3 10 / \ 1 6满足：
左边：
1 < 3 < 6右边：
10 > 8所以合法。
2. 不能只判断左右孩子
很多人第一反应：
判断：
root.left < root root.right > root例如：
5 / \ 1 7 / 4看起来：
1 < 5 7 > 5好像正确。
但是：
4 < 5却出现在 5 的右子树。
所以：
❌ 只判断当前节点是不够的。
BST 的限制是：
所有子树节点都必须满足范围要求。
3. 全局范围约束思想
每个节点都有一个允许范围。
例如：
根节点：
5范围：
(-∞,+∞)右孩子：
7因为它在 5 的右边：
范围：
(5,+∞)7 的左孩子：
4它必须满足：
5 < 4 < 7不成立。
所以：
false三、核心思想：递归维护节点范围
验证 BST 的关键：
给每个节点传递：
当前节点允许的最大值 当前节点允许的最小值定义：
isValid(node,min,max)含义：
判断 node 是否满足：
min < node.val < max然后：
左子树：
最大值变成当前节点：
isValid(node.left,min,node.val)右子树：
最小值变成当前节点：
isValid(node.right,node.val,max)四、递归三部曲
1. 确定递归函数
定义：
boolean isValid(TreeNode root,long min,long max)含义：
判断当前节点是否在：
(min,max)范围内。
2. 确定递归终止条件
如果节点为空：
说明没有违反规则。
返回：
true代码：
if(root == null){ return true; }3. 确定单层递归逻辑
第一步：判断当前节点
如果：
root.val <= min或者：
root.val >= max说明违反 BST。
返回：
false第二步：递归左右子树
左子树：
范围：
(min,root.val)右子树：
范围：
(root.val,max)代码：
return isValid(root.left,min,root.val) && isValid(root.right,root.val,max);五、解法：递归法（面试首选 ✅）
class Solution { public boolean isValidBST(TreeNode root) { return check(root,Long.MIN_VALUE,Long.MAX_VALUE); } private boolean check(TreeNode root,long min,long max){ // 空节点一定合法 if(root == null){ return true; } // 当前节点越界 if(root.val <= min || root.val >= max){ return false; } // 判断左右子树 return check(root.left,min,root.val) && check(root.right,root.val,max); } }六、过程图解
例如：
5 / \ 1 7 / 6第一次：
根节点：
5范围：
(-∞,+∞)满足。
左子树：
1范围：
(-∞,5)满足。
右子树：
7范围：
(5,+∞)满足。
7 的左节点：
6范围：
(5,7)满足。
最终：
true七、复杂度分析
时间复杂度：O(N)
原因：
每个节点访问一次。
所以：
O(N)空间复杂度：O(H)
递归调用栈取决于树高度。
平衡树：
O(logN)最坏链状树：
O(N)所以：
O(H)八、常见错误与避坑指南
❌ 错误一：只判断左右孩子
错误思想：
root.left.val < root.val root.right.val > root.val例如：
5 / \ 1 8 / 4局部看：
4 < 8正确。
但是：
4 < 5不符合右子树要求。
❌ 错误二：使用 int 保存范围
错误：
int min=Integer.MIN_VALUE; int max=Integer.MAX_VALUE;如果节点值刚好：
-2147483648会出现边界问题。
推荐：
long使用：
Long.MIN_VALUE Long.MAX_VALUE❌ 错误三：没有处理重复值
BST 要求：
严格：
左 < 根 < 右所以：
5 / 5不是 BST。
判断：
<= >=不能写：
< >九、另一种经典方法：中序遍历
二叉搜索树有一个重要性质：
中序遍历结果一定是严格递增数组。
例如：
2 / \ 1 3中序：
1 2 3递增。
所以可以：
遍历节点：
保存前一个节点值。
如果：
当前值 <= 前一个值说明不是 BST。
代码：
class Solution { long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root){ if(root == null){ return true; } if(!isValidBST(root.left)){ return false; } if(root.val <= pre){ return false; } pre = root.val; return isValidBST(root.right); } }十、面试高频追问
1️⃣ 为什么不能只比较左右孩子？
因为 BST 的限制是：
整棵子树范围不是：
当前两个孩子2️⃣ 为什么需要 long？
因为节点范围可能达到：
Integer.MIN_VALUE Integer.MAX_VALUE使用 long 可以避免边界错误。
3️⃣ 两种方法哪个更好？
递归范围法：
优点：
- 思路直观
- 可以扩展到其他树约束问题
中序遍历：
优点：
- 利用了 BST 特性
- 代码更简洁
面试中两种都可以。
总结
LeetCode 98 的核心不是判断：
左孩子 < 根 < 右孩子而是维护：
每个节点所在的合法范围递归过程中不断缩小范围：
根节点 ↓ 限制左右子树范围 ↓ 继续递归判断