Java：如何找出破坏二叉搜索树的违规节点？

我正在实现checkBSTValidity方法，该方法需返回破坏二叉搜索树（BST）的节点，若不存在违规节点则返回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()方法，该方法接收树的根节点作为参数，返回破坏树结构的违规节点。违规节点分为三类：

• 位于某祖先节点左子树中，但键值小于该祖先节点的节点
• 位于某祖先节点右子树中，但键值大于该祖先节点的节点
• left或right字段指向祖先节点的节点

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