检查 [1, null, 1] 和 [1, 1] 是否是有效的二叉搜索树

Question

[1, null, 1] 和 [1, 1] 可能的二叉搜索树是什么？会有什么不同吗？

我的代码将 [1, 1] 验证为 BST 而不是 [1, null, 1]，我不明白为什么...

bool isBST(TreeNode* root, int max, int min){
    if(!root)
        return true;
    if((max!= NULL && max<=root->val) || (min!= NULL && min>root->val))
        return false;
    if(!isBST(root->left, root->val, min) || !isBST(root->right, max, root->val))
        return false;
    return true;
}
bool isValidBST(TreeNode* root) {
    int min =NULL, max = NULL;
    return isBST(root, NULL, NULL);
}

为什么我的代码 return [1, null, 1] 不正确？

Answer 1

数组格式通常是树中值的广度优先顺序，其中 null 是没有节点的占位符。

所以例如 [1, 1] 是这棵树的表示：

      1
     /
    1

而[1, null, 1]是这棵树的代表：

       1
      / \
   null  1

即：

       1 
        \
         1

另一个更大的例子：[10, 5, 8, 2, null, 6, null, 1, 3, null, 7]代表：

所以，是的，[1, 1] 和 [1, null, 1] 是有区别的。

你的代码不认为第二个有效的原因是因为在这一行中进行的比较：

if((max!= NULL && max<=root->val) || (min!= NULL && min>root->val))
//                   ^^

您应该允许一个值等于到 max，因此更正如下：

if((max!= NULL && max< root->val) || (min!= NULL && min>root->val))

一些其他备注：

我觉得你的函数首先接受 max 参数然后是 min 令人困惑。考虑改变这两个参数的顺序。
使用 NULL 作为 min 和 max 的初始值可能会在您的树恰好具有等于 [=25 的值时导致问题=]（在大多数环境中，0 等于 NULL）。考虑分别使用 INT_MIN 和 INT_MAX 作为初始值，然后你也可以在你的 isBST 函数中删除额外的条件。

检查 [1, null, 1] 和 [1, 1] 是否是有效的二叉搜索树

Checking that [1, null, 1] and [1, 1] are valid Binary Search Trees

c

binary-tree

binary-search-tree