algorithm - 试图确定一棵树是否是有效的二叉搜索树

Question

下面的代码通过了我们尝试确定树是否为有效 BST 的所有测试用例。

public static boolean validateBst(BST tree) {
    return isValid(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public static boolean isValid(BST tree, int min, int max) {
    if (tree == null) {
        return true;
    }

    if (tree.value < min || tree.value >= max) {
        return false;
    }

    return isValid(tree.left, min, tree.value) && isValid(tree.right, tree.value, max);
}

上面的代码检查树是否是有效的 BST。逻辑很简单，如果一棵树为空，那么它就是 BST。如果树的值小于最小值且大于最大值，我们将返回 false，因为它不是有效的 BST 条件。

我遇到的问题是当我更改以下行时:

if (tree.value < min || tree.value >= max) {
    return false;
}

以下内容

if (tree.value > min && tree.value < max) {
    return true
}

代码没有通过所有的测试用例。这让我感到困惑，因为我觉得这两种说法都在说同一件事。

第一个 if 语句是说如果树/节点的值小于最小值或大于最大值那么你不是一个有效的 BST，第二个语句是说你的值是否在 min 和max 你是一个有效的 bst。

所以请帮助我理解为什么当我更改该行时我的代码没有通过所有测试用例。

是不是因为当我更改该行并返回 true 时，我不会检查树的其余部分？

Answer 1

The code does not pass all the test cases. This is confusing to me because I feel like both statements are saying the same thing.

这里有两个问题，第一个很容易修复，后者需要更广泛的代码重写。

首先，x 的否定是 x≥y。事实上，对于 x ，我们排除了 x = y 的可能性，但如果我们否定该条件，我们应该允许这种情况。

接下来你可以不只返回true如果节点的值介于 min 之间和 max .一颗树。确实:如果节点在边界之间是好消息，但节点的子节点仍然不是有效的二叉搜索树，因此我们需要对子节点进行递归。

因此我们可以这样写:

if(<b>min <= tree.value</b> && tree.value < max){
       return isValid(tree.left,min,tree.value) && isValid(tree.right,tree.value,max);
}
return false;

请注意，根据您具体实现搜索树的方式，您需要更改 tree.value < max至 tree.value <= max以及。因为在一些树中(比如平衡树)，左右子树有时都包含相同的值。然而，如果您的搜索树仅包含不同的值(通常是这种情况)，这可能不是很重要。