Java：如何返回中断二叉搜索树的节点？

Question

正在研究一种方法，该方法应该返回破坏二叉搜索树的节点，或者如果它们都没有返回 null。一些测试用例通过了，但其中一些失败了，我不确定为什么。 到目前为止，这是我的代码：

public static Node checkBSTValidity(Node rootNode) {
    // Your code here (remove the placeholder line below)
    if (rootNode == null) {
       return null;
    }
    
    // Check if left child node is greater than root node
    if (rootNode.left != null && maxValue(rootNode.left) >= rootNode.key) {
       Node node = new Node(maxValue(rootNode.left));
       return node;
    }
    
    // Check if right child node is less than root node
    if (rootNode.right != null && minValue(rootNode.right) <= rootNode.key) {
       Node node = new Node(minValue(rootNode.right));
       return node;
    }
    
    
    Node leftResult = checkBSTValidity(rootNode.left);
    
    if (leftResult != null) {
       return leftResult;
    }
    
    return checkBSTValidity(rootNode.right);
    
}

提交上面的代码后，提示：Invalid tree with left/right child linking to ancestor，我的程序没有输出。它还说：左子键大于父键的无效树不会返回正确的节点。任何帮助将不胜感激！

Answer 1

主要问题是你的函数正在创建一个新的 Node 实例并返回它，而任务是返回一个已经存在于树中的节点。

其次，在每个节点上调用

minValue

和

maxValue

效率不高，因为这样您将多次访问节点，使整个过程的时间复杂度为 O(𝑛log𝑛)，而这可以通过O(𝑛) 时间复杂度。

一个想法是向递归调用传递一个必须包含子树中所有值的“窗口”。最初这个窗口是无界的。如果键的数据类型是

int

，我们可以使用

Integer.MIN_VALUE

和

Integer.MAX_VALUE

作为窗口的边界。

这里是它的编码方式：

private static Node checkBSTValidity(Node rootNode, int low, int high) {
    if (rootNode == null || rootNode.key < low || rootNode.key > high) {
        return rootNode;
    }
    Node node = checkBSTValidity(rootNode.left, low, rootNode.key);
    return node == null ? checkBSTValidity(rootNode.right, rootNode.key, high) 
                        : node;
}

public static Node checkBSTValidity(Node rootNode) {
    return checkBSTValidity(rootNode, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

Answer 2

一些测试用例。

首先，在左子节点大于或等于根节点的情况下，您将返回一个具有左子树最大值的新节点。但是，这个节点不一定是破坏二叉搜索树的节点。相反，您应该返回左子节点本身，因为它是违反 BST 属性的节点。同样，在右子节点小于等于根节点的情况下，应该返回右子节点本身。

其次，您的代码不处理左子节点或右子节点的键分别大于或等于根节点键或小于或等于根节点键的情况。在这种情况下，您应该返回子节点本身，因为它违反了 BST 属性。

这里是修改后的代码，上面提到的更改：

public static Node checkBSTValidity(Node rootNode) {
    if (rootNode == null) {
        return null;
    }

    // Check if left child node violates BST property
    if (rootNode.left != null && rootNode.left.key >= rootNode.key) {
        return rootNode.left;
    }

    // Check if right child node violates BST property
    if (rootNode.right != null && rootNode.right.key <= rootNode.key) {
        return rootNode.right;
    }

    // Recursively check left and right subtrees
    Node leftResult = checkBSTValidity(rootNode.left);
    if (leftResult != null) {
        return leftResult;
    }

    return checkBSTValidity(rootNode.right);
}