Validate Binary Search Tree

给定一棵二叉树，要求判断它是否是一棵合法的二叉搜索树（BST）。

BST 的判断规则：

每个节点的左子树所有节点的值必须严格小于当前节点值
每个节点的右子树所有节点的值必须严格大于当前节点值
左右子树本身也必须是合法 BST

核心思想

要让整棵树是 BST，不只要检查直接子节点是否满足大小关系，还必须检查整棵子树落在合法的值范围内。

例如：

虽然 3 < 4，但 3 < 5，却出现在 5 的右子树，这是不合法的。

所以，判断时必须维护对子树的上界和下界。

算法步骤

递归函数携带当前节点能接受的值区间 [min, max]：

当前节点必须满足 min < node.val < max
递归左子树：最大值缩小为当前节点值
递归右子树：最小值增大为当前节点值

初始时区间为负无穷到正无穷。

代码实现

function isValidBST(root: TreeNode | null): boolean {
  function validate(node: TreeNode | null, min: number, max: number): boolean {
    if (node === null) return true;

    if (node.val <= min || node.val >= max) {
      return false;
    }

    return (
      validate(node.left, min, node.val) &&
      validate(node.right, node.val, max)
    );
  }

  return validate(root, -Infinity, Infinity);
}

时间复杂度： $O(n)$ ，遍历每个节点一次
空间复杂度： $O(h)$ ，h 为树高（递归栈）

Validate Binary Search Tree

核心思想

算法步骤

代码实现

目录