跳到主要内容

LeetCode 98. 验证二叉搜索树

本节目标

将祖先给出的严格上下界传入子树，验证完整 BST 有序约束。

这道题说明构造与二叉搜索树中的 BST 约束必须沿祖先路径传递，而不能只看相邻节点。

查看 LeetCode 原题

题意与边界​

每个节点左子树所有值都严格更小，右子树所有值都严格更大。空树满足定义。节点值可能等于 INT_MIN 或 INT_MAX，因此它们不能作为会排除合法值的严格边界。

严格上下界​

定义 validate(node, lower, upper)：当前节点必须严格落在开区间 (lower, upper) 中。进入左子树时把上界收紧为当前值；进入右子树时把下界收紧为当前值。C++ 用更宽的 long long 边界覆盖所有 int 节点值，Python 用无穷边界。

正确性依据​

根的范围覆盖所有合法节点值。每次向左递归都加入“必须小于当前根”的约束，向右递归都加入“必须大于当前根”的约束，同时保留全部祖先约束。故任一节点都被检查为满足 BST 的完整定义；反之，合法 BST 的每个节点都落在祖先确定的范围内，递归会通过。

代码实现​

C++17
#include <limits>

using namespace std;

class Solution {
private:
    bool validate(TreeNode* node, long long lower, long long upper) {
        if (node == nullptr) {
            return true;
        }
        if (node->val <= lower || node->val >= upper) {
            return false;
        }
        return validate(node->left, lower, node->val) &&
            validate(node->right, node->val, upper);
    }

public:
    bool isValidBST(TreeNode* root) {
        return validate(
            root,
            numeric_limits<long long>::min(),
            numeric_limits<long long>::max()
        );
    }
};

复杂度分析​

每个节点访问一次，时间复杂度为 O(n)。递归栈深度为树高 h，额外空间为 O(h)。

易错点​

  • 只比较节点和直接孩子，漏掉右子树中仍小于根的深层节点。
  • 将相等节点视为合法；本题要求严格不等。
  • 用 INT_MIN、INT_MAX 作 int 边界，误判值取极值的单节点树。

模式迁移​

当约束由祖先不断收紧时，应把允许范围作为递归状态。这个模式也适用于区间合法性、嵌套结构和带上下界的构造问题。