如何验证一棵二叉树是不是有效的二叉搜索树？

简化版

最大的坑：不能只比较每个节点和它的左右孩子——BST 要求的是「左子树所有节点都小于根、右子树所有节点都大于根」，是对整棵子树的约束，不只是直接孩子。两个正确解法：① 中序遍历，检查结果是否严格递增；② 递归时给每个节点传一个合法区间 (min, max)，越界就不合法。

详细版

解法一：中序遍历判递增（最直观）

BST 的中序遍历必然严格升序，反过来「中序升序」也能确保是 BST。所以中序遍历一遍，只要发现当前值 ≤ 前一个值，就不是 BST。

long prev = Long.MIN_VALUE;   // 记录中序前驱的值
boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!isValidBST(root.left)) return false;
    if (root.val <= prev) return false;   // 必须严格大于前驱
    prev = root.val;
    return isValidBST(root.right);
}

解法二：区间约束（上下界）

每个节点必须落在一个合法区间 (low, high) 内。往左走时更新上界为当前值，往右走时更新下界为当前值。

boolean isValidBST(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;  // 越界
    return isValidBST(node.left,  low,       node.val)      // 左子树上界收紧
        && isValidBST(node.right, node.val,  high);         // 右子树下界收紧
}
// 初始调用：isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)

完整版教学

一、最经典的错误：只比父子

很多人第一反应写成「每个节点 > 左孩子、< 右孩子」就行。这是错的。看这个反例：

节点 6 > 5（在右边，合理），6 的左孩子 4 < 6（局部看合理）。但 4 在 5 的右子树里，却比 5 小——违反了 BST！只比父子关系发现不了这个错误。BST 要求的是「右子树里的每一个节点都大于根」，是一个范围约束，不是局部的父子比较。这是本题的核心考点。

二、解法一：中序遍历为什么可靠

BST ⟺ 中序遍历严格递增。这是充要条件，所以中序遍历一趟，维护一个「前驱值 prev」，每访问一个节点就检查它是否严格大于 prev。只要有一处 当前 ≤ prev，就不是 BST。这个方法直接、不易错，是最推荐的思路。

注意用严格大于（<= 判非法）——标准 BST 不允许重复值。若题目允许等值，再按约定放宽。

三、解法二：区间约束为什么正确

换个角度：每个节点都有一个「它必须落在其中」的合法开区间 (low, high)。

根节点区间是 (-∞, +∞)。
往左子树走：所有值必须 < 当前节点，所以上界更新为 node.val，区间变成 (low, node.val)。
往右子树走：所有值必须 > 当前节点，所以下界更新为 node.val，区间变成 (node.val, high)。

这样区间从上往下层层收紧，每个节点都被它所有祖先的约束框住了。回到上面的反例：节点 4 在「5 的右子树」里，它继承的下界是 5，而 4 < 5 越界，立刻被判非法。区间法精确表达了「对整棵子树的约束」。

四、边界值陷阱

区间法要注意节点值等于 int 边界的情况。如果用 int 的 MIN_VALUE/MAX_VALUE 作初始上下界，而树里恰好有等于这些边界的节点，比较会出错。解决办法：用 long 类型做上下界，或改用中序遍历法（配合 Long.MIN_VALUE 初始 prev，或用「是否第一个节点」的标志位规避）。这是面试常设的坑。

五、复杂度

两种解法都是时间 O(n)（每个节点访问一次）、空间 O(h)（递归栈）。中序法还可用迭代或 Morris 遍历把空间进一步优化。

六、常见误区与追问

考点	正确口径
中序法	遍历结果必须严格递增
上下界法	每个节点必须落在祖先传下来的开区间内
边界陷阱	用 long 或 nullable 边界避免 int 溢出

valid(node, low, high):
  if node == null: true
  if node.val <= low || node.val >= high: false
  return valid(node.left, low, node.val)
      && valid(node.right, node.val, high)

验证 BST 要验证祖先约束，不是只验证父子大小关系。

误区：只要左孩子小于根、右孩子大于根就是 BST。 右子树中的所有节点都必须大于根，左子树中的所有节点都必须小于根。
误区：允许相等也算有效 BST。 常见定义要求严格小于和严格大于；若题目允许重复，必须看题目约定。
误区：上下界可以直接用 Integer.MIN_VALUE 和 Integer.MAX_VALUE。 节点值可能正好等于边界，建议用 long 或空边界表示无穷。
追问：中序法为什么正确？ BST 中序是严格升序；反过来，中序严格升序能说明每个节点都满足全局顺序。
追问：上下界法的边界如何传？ 去左子树时上界变成当前值，去右子树时下界变成当前值。
追问：复杂度是多少？ 时间 O(n)，每个节点访问一次；空间 O(h)，h 是递归栈高度。

七、加强记忆

验证 BST 不能只比父子——要保证「左子树全部 < 根、右子树全部 > 根」的范围约束（经典反例：右子树里藏一个比根小的节点）。两解法：中序遍历判严格递增（维护前驱 prev，当前 ≤ prev 即非法）；区间约束（每节点必须落在 (low, high)，左走收紧上界、右走收紧下界）。注意用严格比较、用 long 防边界值溢出。O(n)。

简化版

详细版