一、题目描述给你一个二叉树的根节点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 minInteger.MIN_VALUE; int maxInteger.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 的核心不是判断左孩子 根 右孩子而是维护每个节点所在的合法范围递归过程中不断缩小范围根节点 ↓ 限制左右子树范围 ↓ 继续递归判断