手帐 Blog

主题

复盘 · LC 98 验证二叉搜索树 ​

题目 ​

题意 ​

判断一棵二叉树是否为合法 BST：对每个节点，左子树所有值 < 节点，右子树所有值 > 节点（题目为严格不等）。

  • 空树是 BST。
  • 只和左右孩子比大小不够——孙子也可能越界（经典反例：5 的右孩子 6，6 的左孩子 3）。

涉及算法 ​

标签一句话
上下界递归每个节点带 (low, high)，low < val < high，左传 (low, val)，右转 (val, high)
中序遍历BST 中序严格递增

教程对照：18 · BFS 层序与 BST。昨日相关：108 有序数组转 BST。

评价我的解法 ​

初版（错） ​

我的代码（摘自 98-验证二叉搜索树/index.js，不含测例）：

javascript
var isValidBST = function (root) {
  let isBst = true;
  function bst(root) {
    if (!isBst) {
      return null;
    }
    if (!root) {
      return null;
    }
    const val = root.val;
    const left = bst(root.left);
    if (left && left >= val) {
      isBst = false;
    }
    const right = bst(root.right);
    if (right && right <= val) {
      isBst = false;
    }
    if (!isBst) {
      return null;
    }
    return val;
  }
  if (!isBst) {
    return false;
  }
  bst(root);
  return isBst;
};

问题：

  1. 只和左右子节点的值比，没约束整棵左/右子树相对祖先的范围。本地树 5-4-6(3,7) 会误判为合法。
  2. if (left) 把 0 当假：节点值为 0 时比较被跳过（即便局部比较思路也脆）。
  3. 外层 if (!isBst) return false 在调用 bst 前恒为 true，是死代码。

中序版（能 AC，实现糙） ​

我的代码（摘自 98-验证二叉搜索树/index2.js，不含测例）：

javascript
var isValidBST = function (root) {
  const resArr = [];
  function bst(root) {
    if (!root) {
      return null;
    }
    const left = bst(root.left);
    if (left) {
      resArr.push(left);
    }
    resArr.push(root.val);
    const right = bst(root.right);
    if (right) {
      resArr.push(right);
    }
  }
  bst(root);
  if (resArr.length === 1) {
    return true;
  }
  for (let i = 1; i < resArr.length; i++) {
    const pre = resArr[i - 1];
    const cur = resArr[i];
    if (pre >= cur) {
      return false;
    }
  }
  return true;
};

评价：

  1. 方向对：中序收集再检查严格递增，能抓住「整树 BST」定义，AC 合理。
  2. bst 没有 return val：left/right 恒为 undefined，if (left) push 实际从不执行——等于只靠 resArr.push(root.val) 做中序，歪打正着。
  3. 空间：O(n) 数组可压成「只记前驱」O(1) 额外（不计栈）；单节点特判多余。
  4. 复杂度：时间 O(n)，空间 O(n)。

小结：初版踩了 BST 第一坑（局部父子合法 ≠ 全局合法）；中序救回来了，但应删掉无效的 left/right 回推，或改成上下界递归。

最佳题解 ​

上下界（推荐口述）：

javascript
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  function dfs(node, low, high) {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
  }
  return dfs(root, -Infinity, Infinity);
};

中序只记前驱：

javascript
var isValidBST = function (root) {
  let prev = -Infinity;
  function inorder(node) {
    if (!node) return true;
    if (!inorder(node.left)) return false;
    if (node.val <= prev) return false;
    prev = node.val;
    return inorder(node.right);
  }
  return inorder(root);
};
  • 时间 O(n)，空间 O(h)。
  • 为何更优：上下界直接表达定义；中序前驱版比整表存数组更省、逻辑更干净。

关联题目 ​

题为何相关
108. 将有序数组转换为二叉搜索树合法 BST 的构造面
230. 二叉搜索树中第 K 小的元素中序有序性同一底座
700. 二叉搜索树中的搜索BST 搜索剪枝

一句话带走 ​

验 BST：不能只比左右孩子——要么带上下界递归，要么中序严格递增。