算法 - 验证二叉搜索树

Posted on

1. 题目

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。

有效 BST 定义：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例:

1
2
3
4
5
6
7
8
输入: root = [5,1,4,null,null,3,6]
        5
       / \
      1   4
         / \
        3   6
输出: false
解释: 根节点 5 的右子树里出现 3（< 5），违反 BST 定义。

2. 解题思路

2.1 常见错误：只比较父子

只判断「左子 < 父 < 右子」是不够的——如上图，节点 3 是其父 4 的合法左子，但它位于根 5 的右子树中，必须 > 5。约束是从根一路传递下来的区间。

2.2 上下界递归（正确）

给每个节点维护一个开区间 (min, max)：

  • 根的区间是 (-∞, +∞)。

  • 走向左孩子：上界收紧为父节点值 → (min, node.val)。

  • 走向右孩子：下界收紧为父节点值 → (node.val, max)。

  • 节点值必须严格落在自己区间内，否则非法。

  • 时间复杂度：O(n)，空间复杂度：O(h)。

2.3 中序遍历递增

BST 的中序遍历结果严格递增。迭代中序遍历，比较当前值与前驱值 prev，若 val <= prev 则非法。用 prev 记录上一个访问值即可，天然利用「左→根→右」顺序。

  • 时间复杂度：O(n)，空间复杂度：O(h)。

3. TypeScript 实现

树节点定义：

1
2
3
4
5
6
7
8
9
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0) {
        this.val = val;
        this.left = this.right = null;
    }
}

3.1 上下界递归

1
2
3
4
5
6
7
8
9
10
11
12
function isValidBST(root: TreeNode | null): boolean {
    const check = (node: TreeNode | null, min: number, max: number): boolean => {
        if (!node) return true;
        if (node.val <= min || node.val >= max) return false;
        return (
            check(node.left, min, node.val) &&
            check(node.right, node.val, max)
        );
    };

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

3.2 中序遍历（迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isValidBSTInorder(root: TreeNode | null): boolean {
    const stack: TreeNode[] = [];
    let cur = root;
    let prev = -Infinity;

    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;         // 一路向左
        }
        cur = stack.pop()!;
        if (cur.val <= prev) return false; // 非严格递增
        prev = cur.val;
        cur = cur.right;
    }

    return true;
}

4. 面试延伸

  • 为什么用严格 <、>（而非 <=）：BST 定义里子树值必须严格小于/大于，相等也算非法；用 Infinity 做初始边界可避免「节点值恰好等于 INT_MIN/INT_MAX」的坑（用 null 表示无边界更稳妥）。
  • 传递区间 vs 传递父指针：区间法最直观；中序法把「树问题」转成「有序序列问题」是常用思维。
  • 关联题：BST 第 k 小、把有序数组转 BST、LCA of BST 都依赖「中序有序」或「值域可二分」性质。

难度：中等 | LeetCode 98 | BST 性质 / 遍历