验证二叉搜索树 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

有效 BST 定义如下：

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

示例 1

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

输出：true

示例 2

输入：root = [5,1,4,null,null,3,6]

输出：false

根节点 5，右子树中节点 4 小于 5，违反 BST 性质。

💭 模拟答题者思考

1. 我先想：只比较「当前节点和直接子节点」够不够？不够——比如 [5,1,4,null,null,3,6] 中 3 在 5 的右子树里，但 3 < 5。

2. 重复在哪里？每个节点不仅要大于左孩子、小于右孩子，还要落在「祖先链」允许的区间内。

3. 优化：DFS 时携带合法区间 (low, high)，当前值必须在开区间内。

4. 递归左子树时上界收紧为 root.val；递归右子树时下界收紧为 root.val。

5. 空节点视为合法；任一子树不合法则整棵树不合法。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`low`	int / long	定义：当前子树所有节点值的下界（不含）维护：进入左子树时不变；进入右子树时更新为 `root.val` 更新：递归右子树传 `low=root.val`
`high`	int / long	定义：当前子树所有节点值的上界（不含）维护：进入右子树时不变；进入左子树时更新为 `root.val` 更新：递归左子树传 `high=root.val`
`root.val`	int	定义：当前节点的值维护：必须满足 `low < root.val < high` 更新：不满足则整棵子树无效，立即返回 false

⌨️ 落码步骤

1. 定义 dfs(node, low, high)：空节点返回 true

2. 若 node.val <= low 或 node.val >= high，返回 false

3. 左子树传 (low, node.val)，右子树传 (node.val, high)

4. 左右子树都合法才返回 true

5. 入口调用 dfs(root, -∞, +∞)，注意用 long 避免 INT_MIN/INT_MAX 边界溢出

💻 代码实现

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def dfs(node, low, high):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return (
                dfs(node.left, low, node.val)
                and dfs(node.right, node.val, high)
            )

        return dfs(root, float("-inf"), float("inf"))

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, LONG_MIN, LONG_MAX);
    }

    bool dfs(TreeNode* node, long low, long 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);
    }
};
// 时间 O(n)，空间 O(n)（递归栈）

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)（递归栈）

⚠️ 常见坑

❗ 只比较父子节点：右子树里可能出现小于根的值（经典反例 [5,1,4,null,null,3,6]）。

❗ 边界用 <= / >= 判非法：BST 要求严格小于/大于，相等也不合法。

❗ C++ 用 INT_MIN/INT_MAX 作初始边界时，节点值等于边界会溢出比较；应使用 long 或中序遍历 + prev。

🔍 必测边界 Case

Case 1：单节点

root = [1] → true

Case 2：相等值

root = [2,2,2] → false（左孩子等于根）

Case 3：INT 边界

root = [2147483647] → true（long 边界不会误判）