验证BST时代码判定[1,1]有效[1,null,1]无效的原因分析

两个数组对应的BST结构差异 #

层序遍历序列对应的二叉树结构完全不同：

• [1, 1]：根节点值为1，左子节点值为1，右子节点为空
• [1, null, 1]：根节点值为1，左子节点为空，右子节点值为1

代码问题分析 #

你提供的代码存在两个核心错误，导致判断结果不符合预期：

1. 边界参数的类型和判断逻辑错误 #

你用int类型存储边界，并且直接和NULL比较，这是完全不符合C语言规范的：

• NULL本质是void*类型的指针常量，赋值给int类型时会被隐式转换为整数0，你无法区分「无初始边界」和「边界值刚好为0」的场景，会出现大量逻辑误判。
• 你在isValidBST中定义的int min =NULL, max = NULL;是完全无效的废代码，调用递归函数时你直接传了NULL，和这两个变量没有关联。

2. 相等值的判断逻辑不一致 #

BST的重复值规则需要统一：要么严格不允许重复，要么重复值统一存放在左子树/右子树，你的代码左右判断逻辑不一致：

• 左子树判断条件max<=root->val：只要左子节点值等于父节点值，就会判定为非法
• 右子树判断条件min>root->val：右子节点值等于父节点值时不会触发非法判定

如果你的测试结果是[1, 1]判定合法、[1, null, 1]判定非法，说明你实际写代码时还可能存在递归参数顺序写反的问题，把左右子树的边界传反了。

修复方案 #

建议用长整型极值作为初始边界，避免判断空边界的问题，严格BST的实现代码如下：

#include <limits.h>
bool isBST(TreeNode* root, long long min_val, long long max_val) {
    if (!root) return true;
    // 严格BST要求节点值必须大于下界、小于上界
    if (root->val <= min_val || root->val >= max_val) return false;
    // 左子树上界为当前节点值，右子树下界为当前节点值
    return isBST(root->left, min_val, root->val) && isBST(root->right, root->val, max_val);
}
bool isValidBST(TreeNode* root) {
    return isBST(root, LLONG_MIN, LLONG_MAX);
}

如果允许重复值，可根据规则调整判断条件：

• 重复值统一放左子树：将右子树的判断改为root->val > max_val，左子树保持root->val <= min_val
• 重复值统一放右子树：将左子树的判断改为root->val < min_val，右子树保持root->val >= max_val

内容的提问来源于stack exchange，提问作者Abhishek Singh