#98
中等
低频
递归中序验证二叉搜索树
这是一道围绕树、二叉树展开的高频练习。建议先掌握「递归中序」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
题目分析
给你一棵二叉树，要求判断它是不是一棵合法的二叉搜索树。
二叉搜索树的要求是：
- 左子树所有节点都比当前节点小
- 右子树所有节点都比当前节点大
- 左右子树本身也都必须是二叉搜索树
一句话概括：
BST 的合法性是全局范围约束，不是局部比较一下左右孩子就够了。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：对二叉搜索树做中序遍历，结果必须严格递增；一旦出现逆序，就不是合法 BST。
推荐代码
推荐解法：递归中序
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： 对二叉搜索树做中序遍历，结果必须严格递增；一旦出现逆序，就不是合法 BST。
class Solution {
private Long prev = null;
public boolean isValidBST(TreeNode root) {
return inorder(root);
}
private boolean inorder(TreeNode node) {
if (node == null) {
return true;
}
if (!inorder(node.left)) {
return false;
}
if (prev != null && node.val <= prev) {
return false;
}
prev = (long) node.val;
return inorder(node.right);
}
}结构化讲解
面试时怎么讲
开场思路
这题我会利用 BST 的中序遍历结果必须严格递增这个性质来验证。
核心过程
- 递归做中序遍历，先看左子树。
- 访问当前节点时，把它和上一个访问到的值比较。
- 如果当前值不大于前驱值，直接返回 false。
- 否则更新前驱，继续递归右子树。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)。
面试补一句：这题高频误区是只看局部父子关系，没有验证全局范围。
核心思路
验证 BST 最稳定的思路，是使用它的核心性质：中序遍历结果严格递增。只要遍历过程中发现当前值不大于前一个值，就能立即判错。
步骤讲解
1
做中序遍历
按左子树、当前节点、右子树的顺序递归访问整棵树。
为什么这样做：BST 的中序遍历天然对应有序序列。
对应代码提示：if (!dfs(node.left)) return false;
2
维护前一个访问值
每访问到一个节点，都和前一个中序节点值比较，必须严格更大。
为什么这样做：BST 不能出现重复或逆序值，否则有序性被破坏。
对应代码提示：if (prev != null && node.val <= prev) return false;
3
更新前驱后继续遍历右子树
当前节点合法后，把它记成新的前驱，再去处理右子树。
为什么这样做：右子树所有节点都必须大于当前节点，因此比较链需要持续向后传递。
对应代码提示：prev = node.val;
易错点
只比较父子节点大小
BST 约束是整棵子树范围，不是只看直接父子关系。
正确理解：优先用中序严格递增或上下界递归来验证全局约束。
把重复值当成合法
题目要求左子树所有值小于根、右子树所有值大于根，不能相等。
正确理解：比较时使用严格大于，不是大于等于。
前驱值作用域没处理好
如果前驱状态没跨递归层共享，中序比较就会失效。
正确理解：让
prev 成为外部变量或通过引用在递归间传递。复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比逐层口头判断更严谨，也比显式存完整中序数组更省空间。
适用判断：题目直接考 BST 合法性时，中序严格递增是最稳的切入点。
额外提醒
- 真正需要验证的是全局有序性，而不是局部大小关系。