Java：如何返回破坏二叉搜索树的节点？

研究一个应该返回破坏二叉搜索树的节点的方法，如果没有一个节点返回破坏二叉搜索树的节点，则返回 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);
    
}

提交上面的代码后，它显示：无效的树，左/右子节点链接到祖先，并且我的程序不产生任何输出。它还说：左子键大于父键的无效树不会返回正确的节点。任何帮助，将不胜感激！

编辑：对于挑战，它说要实现 checkBSTValidity() ，它将树的根节点作为参数并返回违反树的节点。违规节点将是以下三种情况之一：

1. 祖先左子树中具有较小键的节点
2. 祖先右子树中具有更大键的节点
3. 左侧或右侧字段引用祖先的节点

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

但在评论中，您还提到该函数应该检查子节点是否与其祖先之一是相同的节点引用。您的代码中没有对此进行规定。我建议为此目的使用 HashSet，每次重复到其中一个子树时都可以向其中添加一个节点。

最后调用效率不高minValue and maxValue在每个节点上，这样您将多次访问节点，整个过程的时间复杂度为 O(????log????)，而这可以用 O(????) 时间复杂度来完成。

一种想法是向递归调用传递一个“窗口”，该窗口必须包含子树中的所有值。最初这个窗口是无界的。如果键的数据类型是int，我们可以使用Integer.MIN_VALUE and Integer.MAX_VALUE作为窗口的边界。

下面是它的编码方式：

private static Node checkBSTValidity(Node rootNode, int low, int high,
                                     HashSet<Node> ancestors) {
    if (rootNode == null) {
        return null;
    }
    // Track each ancestor as we traverse down the tree
    ancestors.add(rootNode);
    // Any violation?
    if (rootNode.key < low || rootNode.key > high 
            || ancestors.contains(rootNode.left) 
            || ancestors.contains(rootNode.right)) {
        return rootNode;
    }
    // Check the sub trees
    Node node = checkBSTValidity(rootNode.left, low, rootNode.key, ancestors);
    if (node == null) {
        node = checkBSTValidity(rootNode.right, rootNode.key, high, ancestors);
    }
    ancestors.remove(rootNode); // Backtrack
    return node;
}

public static Node checkBSTValidity(Node rootNode) {
    HashSet<Node> ancestors = new HashSet<>();
    return checkBSTValidity(rootNode, Integer.MIN_VALUE, Integer.MAX_VALUE,
                            ancestors);
}

收集集合中的所有祖先可能看起来有些过分，但是需要跟踪所有祖先，以防树中允许重复的键。我们可以在树中建立一条路径，其中的节点都具有相同的键，并且子节点是对这些祖先之一的引用。在这种情况下，密钥不会违反 BST 属性，但仍应检测反向引用。