#98. 验证二叉搜索树

• LeetCode：原题
• 难度：中等
• 归类：二叉树、深度优先搜索、二叉搜索树
• 主解法：中序遍历

#先给结论

二叉搜索树的中序遍历结果必须是严格递增序列。因此按“左子树 → 当前节点 → 右子树”的顺序遍历，只需记录前一个访问的节点；一旦出现 prev.val >= root.val，整棵树就不是合法的二叉搜索树。

这里的“严格”很重要：题目要求左子树所有节点都小于根节点、右子树所有节点都大于根节点，所以重复值也不合法。

#题目描述

给定一棵二叉树的根节点 root，判断它是否为有效的二叉搜索树。

有效二叉搜索树需要满足：

1. 节点的左子树只包含严格小于当前节点的值；
2. 节点的右子树只包含严格大于当前节点的值；
3. 左右子树本身也必须是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：值为 4 的节点位于根节点 5 的右子树中，但 4 < 5。

#问题本质

最容易犯的错误，是只比较父节点与它的两个直接子节点。例如下面这棵树：

    5
   / \
  1   6
     / \
    3   7

节点 3 < 6，所以它满足与父节点 6 的局部关系；但它处于根节点 5 的右子树中，必须同时满足 3 > 5，因此整棵树并不是二叉搜索树。

也就是说，BST 是一个对子树中所有节点生效的全局约束，不能只检查相邻节点。中序遍历恰好把这个全局约束转换为一维序列的严格递增约束。

#数据结构与因果链

1. 对左子树做中序遍历；如果左子树已经不合法，立即返回 false。
2. 此时 prev 是中序序列中当前节点的前驱。
3. 比较 prev.val 和当前节点值：若前者大于或等于后者，严格递增被破坏。
4. 将当前节点赋给 prev，继续遍历右子树。

遍历过程中始终保持下面的不变量：

prev 指向已经完成中序遍历的节点中最后访问的节点，并且已访问序列严格递增。

#示例推演

以 root = [5,1,4,null,null,3,6] 为例，中序访问顺序是 1 → 5 → 3 → 4 → 6：

虽然节点 3 与其父节点 4 的关系正确，但中序遍历仍能发现它违反了祖先节点 5 施加的下界。

#逐步图解：中序遍历到底在做什么

中序遍历的顺序固定为：

左子树 → 当前节点 → 右子树

先看一棵合法的二叉搜索树：

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

代码不会一到节点 4 就比较它，而是不断向左走，先找到最小的节点 1。

#第 1 步：从根节点一路向左

        4              dfs(4)
      /   \               ↓ 先走左边
    [2]    6            dfs(2)
    / \   / \              ↓ 继续走左边
  [1]  3 5   7          dfs(1)

当前节点：1
prev：null
已访问序列：[]

1 没有左孩子，而且 prev 还是 null，说明它是第一个访问的节点，不需要比较。访问后令 prev = 1。

已访问序列：[1]
prev：1

#第 2 步：回到节点 2

节点 1 的左右子树都处理完后，递归返回节点 2：

        4
      /   \
    [2]    6       比较：prev.val < node.val
    / \   / \             1 < 2  ✓
   1   3 5   7

当前节点：2
prev：1
已访问序列：[1]

比较通过，访问 2，然后更新 prev = 2。

已访问序列：[1, 2]
prev：2

#第 3 步：访问节点 3

处理完节点 2 自身后，进入它的右子树：

        4
      /   \
     2     6       比较：2 < 3  ✓
    / \   / \
   1  [3] 5   7

当前节点：3
prev：2
已访问序列：[1, 2]

比较通过，更新 prev = 3，已访问序列变成 [1, 2, 3]。

#第 4 步：回到根节点 4

根节点 4 的整棵左子树已经访问完：

       [4]          比较：3 < 4  ✓
      /   \
     2     6
    / \   / \
   1   3 5   7

当前节点：4
prev：3
已访问序列：[1, 2, 3]

比较通过，更新 prev = 4。

#第 5～7 步：遍历右子树

按照同样的规则继续访问 5、6、7：

第 5 步：prev = 4，当前节点 = 5，4 < 5  ✓
第 6 步：prev = 5，当前节点 = 6，5 < 6  ✓
第 7 步：prev = 6，当前节点 = 7，6 < 7  ✓

最终中序序列：[1, 2, 3, 4, 5, 6, 7]

每次都是“前一个值 < 当前值”，整个序列严格递增，所以返回 true。

#反例：在哪一步发现错误

再看下面这棵树：

        5
      /   \
     1     6
          / \
         3   7

如果只比较父子节点，会发现 3 < 6，看起来没有问题。但中序遍历为：

1 → 5 → 3 → 6 → 7

逐步比较：

第 1 步：当前节点 = 1，prev = null，不比较；更新 prev = 1
第 2 步：当前节点 = 5，prev = 1，1 < 5  ✓；更新 prev = 5
第 3 步：当前节点 = 3，prev = 5，5 >= 3 ✗；立即返回 false

错误发生时可以画成：

        5  ← prev
      /   \
     1     6
          / \
        [3]  7
         ↑
      当前节点

中序序列已经变成：[1, 5, 3]
                         └─ 不是严格递增

3 虽然小于父节点 6，却位于根节点 5 的右子树中，本应大于 5。中序遍历把这种不容易直接看出的祖先约束，转换成了非常直观的相邻元素比较。

因此，代码中的这一段可以理解为：

// 中序遍历已经访问过的最后一个值，必须小于当前值
if (prev !== null && prev.val >= node.val) {
  return false;
}
prev = node; // 当前节点成为下一次比较的“前一个节点”

#代码实现

#JavaScript：中序遍历

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  // 记录中序遍历中上一个访问的节点，用于检查序列是否严格递增
  let prev = null;

  const dfs = (node) => {
    // 空子树满足二叉搜索树的定义
    if (node === null) {
      return true;
    }

    // 中序遍历：先验证左子树
    if (!dfs(node.left)) {
      return false;
    }

    // 当前节点必须严格大于中序遍历中的前一个节点；重复值也不合法
    if (prev !== null && prev.val >= node.val) {
      return false;
    }

    // 当前节点将成为后续节点的中序前驱
    prev = node;

    // 最后验证右子树，并将验证结果向上返回
    return dfs(node.right);
  };

  return dfs(root);
};

#代码与思路对照

短路返回不仅能提前结束遍历，也能保证发现逆序后，false 会一直传递到最外层。

#正确性证明

可以从充要条件的两个方向说明：

• 若一棵树是二叉搜索树：左子树的所有值都小于根节点，右子树的所有值都大于根节点，左右子树也分别满足该性质，所以它的中序遍历序列必然严格递增。
• 若一棵二叉树的中序遍历序列严格递增：任意节点左子树中的节点都出现在它之前，值必然更小；右子树中的节点都出现在它之后，值必然更大。该性质对每个节点都成立，所以它是二叉搜索树。

代码恰好逐项验证中序序列是否严格递增，因此返回结果正确。

#复杂度分析

设节点数为 n，树高为 h：

• 时间复杂度：O(n)。最坏情况下每个节点访问一次；发现逆序时可能提前结束。
• 空间复杂度：O(h)。空间来自递归调用栈；平衡树为 O(log n)，退化成链表时为 O(n)。

prev 只占 O(1) 额外空间，不能把递归栈忽略后直接写成整体 O(1)。

#替代解法：上下界递归

另一种直接对应 BST 定义的写法，是为每个节点维护允许的开区间 (lower, upper)：

• 进入左子树时，上界收紧为当前节点值；
• 进入右子树时，下界收紧为当前节点值；
• 当前节点不在开区间内时，立即返回 false。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  // 验证当前节点的值是否处于祖先节点共同限定的开区间内
  const dfs = (node, lower, upper) => {
    // 空子树不违反任何边界约束
    if (node === null) {
      return true;
    }

    // 使用开区间排除越界值和重复值
    if (node.val <= lower || node.val >= upper) {
      return false;
    }

    return (
      // 左子树中的所有节点都必须小于当前节点
      dfs(node.left, lower, node.val) &&
      // 右子树中的所有节点都必须大于当前节点
      dfs(node.right, node.val, upper)
    );
  };

  // 根节点最初不受有限上下界约束
  return dfs(root, -Infinity, Infinity);
};

该方法的时间复杂度同样是 O(n)，空间复杂度同样是 O(h)。它显式表达了祖先节点对当前节点的约束；中序遍历则代码更短，只维护一个前驱节点。

#边界与陷阱

• 空树和单节点树：都满足 BST 定义，应返回 true。
• 重复值：BST 要求严格小于或严格大于，因此重复值必须返回 false。
• 只检查左右孩子：会漏掉节点与更高层祖先之间的冲突。
• 遍历顺序写错：必须先递归左子树，再比较当前节点，最后递归右子树。
• 把 prev 初始化为固定数值：若初始化为 0 或某个题目边界值，可能误判第一个节点；使用 null 更稳妥。
• 上下界使用闭区间：判断必须是 <= lower 或 >= upper，否则会错误接受重复值。
• 连续多次调用时共享状态：若 prev 放在函数外部，下一次调用可能继承上一次结果；应在 isValidBST 内初始化。

#面试官递进追问

#1. 为什么不能只比较父节点和直接子节点？

因为一个节点需要满足所有祖先施加的约束。右子树中的每个节点不仅要符合与父节点的关系，还必须严格大于该子树对应的祖先下界；局部正确不能推出全局正确。

#2. 中序遍历为什么能验证 BST？

BST 的中序遍历序列严格递增，反过来，中序序列严格递增也能保证每个节点的左子树都更小、右子树都更大。因此“是 BST”与“中序序列严格递增”等价。

#3. 为什么判断条件是 >=，而不是 >？

题目中的 BST 不允许重复值。当前节点与前驱相等时，序列不是严格递增，也应判定为非法。

#4. 空间复杂度是 O(log n) 还是 O(n)？

准确写法是 O(h)。平衡树高度为 O(log n)；最坏情况下树退化为链表，高度为 O(n)。

#5. 如何避免深树导致递归栈溢出？

可以用显式栈实现迭代中序遍历，仍然维护 prev。渐进空间复杂度仍为 O(h)，但不会消耗语言运行时的递归调用栈。

#6. 中序遍历与上下界递归如何取舍？

中序遍历状态少、实现简洁；上下界递归更直接地体现 BST 的定义和祖先约束。两者的时间、空间复杂度相同，面试中选择自己更容易一次写对并证明的方案即可。

#常见错误回答

• “左孩子小、右孩子大，所以递归检查孩子即可”：没有把祖先约束传递给后代。
• “中序遍历有序即可”：应明确是严格递增，否则会错误接受重复值。
• “空间复杂度是 O(1)”：忽略了递归调用栈。
• 使用数组保存完整中序结果再检查：虽然正确，但需要 O(n) 额外空间；实际上只保留前一个节点就够了。

#可迁移总结

• 遇到 BST，优先想到两个等价视角：中序遍历严格递增、每个节点位于祖先传下来的合法区间内。
• 局部父子关系不足以验证带祖先约束的树结构。
• 中序遍历若只依赖相邻元素，通常可以用一个 prev 替代完整数组。
• 树上递归的空间复杂度通常写成 O(h)，再分别说明平衡和退化情况。

#刷题后自测

1. 为什么 [5,1,6,null,null,3,7] 不是二叉搜索树？只比较父子节点会得到什么错误结论？
2. 中序遍历方案中的 prev 在每次比较前具体表示什么？
3. 如果改用上下界递归，进入左右子树时应该分别更新哪个边界？
4. 为什么上下界必须是开区间，而不是闭区间？
5. 能否写出迭代中序遍历版本，并说明它的空间复杂度？