Frontend Interview

Appearance

98. 验证二叉搜索树 ​

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/

代码 ​

ts
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isValidBST(root: TreeNode | null): boolean {
    return dfs(root, -Infinity, Infinity);
};

function dfs(node: TreeNode | null, min: number, max: number) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
}

思路 ​

使用递归 + 区间限制的方法验证二叉搜索树：

  1. 对于每个节点，维护一个有效值区间 (min, max)
  2. 根节点的区间为 (-∞, +∞)
  3. 对于左子树，更新区间为 (min, node.val)
  4. 对于右子树，更新区间为 (node.val, max)
  5. 如果节点值不在有效区间内，返回 false

关键点 ​

  • 二叉搜索树的定义：左子树所有节点值 < 根节点值 < 右子树所有节点值

  • 不能只比较父子节点，需要保证整个子树的值都在有效区间内

  • 使用 <= 和 >= 判断，因为 BST 中不允许有重复值

  • 时间复杂度 O(n)，其中 n 是节点数量，需要遍历所有节点

  • 空间复杂度 O(n)，递归调用栈的深度，最坏情况下为树的高度