(每日一道算法题)验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode） 

算法思路：中序遍历与值比较

二叉搜索树的关键特性是：​​中序遍历结果是有序序列​​。利用这一性质，我们可以设计以下算法：

1. 对二叉树进行中序遍历（左-中-右）。
2. 在遍历过程中，记录前一个访问到的节点值。
3. 每次访问新节点时，确保它的值大于前一个节点值。
4. 若遍历过程中始终满足递增关系，则该树是BST。

实现要点

• ​​全局变量存储前驱值​​：初始化一个极小值（Long.MIN_VALUE），避免与节点最小值冲突。
• ​​递归中序遍历​​：深度优先搜索自然实现中序序列。
• ​​中断机制​​：一旦发现不满足条件，立即返回false。

代码实现 

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {long prev = Long.MIN_VALUE;  // 存储中序遍历的前驱值public boolean isValidBST(TreeNode root) {if (root == null)  // 空树是BSTreturn true;// 递归检查左子树if (!isValidBST(root.left)) return false;// 检查当前节点值是否大于前驱值if (root.val <= prev) return false;prev = root.val;  // 更新前驱值// 递归检查右子树return isValidBST(root.right);}
}

关键解析

代码片段	功能说明
long prev = Long.MIN_VALUE;	使用long类型避免与Integer.MIN_VALUE冲突
if (!isValidBST(root.left))	优先递归左子树，实现中序遍历顺序
if (root.val <= prev) return false;	确保当前值大于前驱值，否则直接判定失败
prev = root.val;	更新前驱值，为后续节点比较做准备
return isValidBST(root.right);	最后检查右子树并返回结果

复杂度分析

• ​​时间复杂度​​：O(N)，每个节点恰好访问一次。
• ​​空间复杂度​​：O(H)，递归栈深度取决于树高H，最坏情况（链表结构）为O(N)。

处理边界情况

1. ​​空树处理​​：空树被视为有效的BST。
2. ​​单节点树​​：没有左右子树，天然满足BST条件。
3. ​​极值处理​​：使用Long.MIN_VALUE防止节点值为Integer.MIN_VALUE时误判。

拓展思考

这种方法利用了BST的中序特性，实际上也反映了二叉搜索树的本质：​​元素的有序存储​​。实际应用中，BST常用于实现快速查找的数据结构，如TreeMap。理解其有效性判断对构建正确算法至关重要。

通过中序遍历递归实现，我们既保证了代码简洁性，又确保了逻辑的严密性，有效解决了二叉搜索树的验证问题