BST插入函数未通过测试求助：返回类型与构造器参数不符

我实现了二叉搜索树的insert函数，但无法通过部分测试用例，代码如下：

@Override
public TreeElement<T> insert(T value, Comparator<T> comp) {
    if(value == null)
        throw new NullPointerException("null not supported");

    int comparator = comp.compare(value, info);
    //iseti uazro bagebi mepareba auaa
    if(comparator > 0){
        if(right == null)
            return new InnerNode<>(value, new Leaf<>(value), left);
        else {
            return right = right.insert(value, comp);
        }
    }else if(comparator < 0){
        if(left == null)
            return new InnerNode<>(value, right, new Leaf<>(value));
        else {
            return left = left.insert(value, comp);
        }
    }
    return this;
}

遇到的具体问题：

• InnerNode类中参数为[Object, Comparator]的insert方法返回类型未按预期实现；
• InnerNode类中参数为[Object]的构造器参数未按预期实现。

问题1：返回类型不符合预期的修复 #

当前代码在递归插入子节点后，错误地返回了更新后的子节点（right或left），但二叉搜索树的insert方法预期返回修改后的当前节点（当前节点的子节点发生变化，但节点本身并未被替换）。

修复方式：在递归更新子节点后，返回this而不是子节点本身。

问题2：构造器参数错误的修复 #

创建新InnerNode时存在两个核心错误：

1. 错误地将插入的value作为新节点的存储值，实际应保留当前节点的info，仅将新值作为子节点添加；
2. 构造器的参数顺序颠倒，子节点的左右位置不符合BST规则。

假设InnerNode的构造器签名为InnerNode(T info, TreeElement<T> left, TreeElement<T> right)（存储值、左子树、右子树），正确逻辑是：当子树为空时，创建新叶子节点作为当前节点的子节点，然后返回当前节点。

修复后的完整代码 #

@Override
public TreeElement<T> insert(T value, Comparator<T> comp) {
    if (value == null)
        throw new NullPointerException("null not supported");

    int cmp = comp.compare(value, info);
    if (cmp > 0) {
        if (right == null) {
            // 右子树为空，添加新叶子节点作为右子节点
            right = new Leaf<>(value);
            return this;
        } else {
            // 递归插入右子树，更新右子节点后返回当前节点
            right = right.insert(value, comp);
            return this;
        }
    } else if (cmp < 0) {
        if (left == null) {
            // 左子树为空，添加新叶子节点作为左子节点
            left = new Leaf<>(value);
            return this;
        } else {
            // 递归插入左子树，更新左子节点后返回当前节点
            left = left.insert(value, comp);
            return this;
        }
    }
    // 值已存在，直接返回当前节点
    return this;
}

补充：Leaf节点的insert实现（必要时） #

叶子节点插入新值后会变为内部节点，因此Leaf类的insert方法需返回新的InnerNode，示例如下：

@Override
public TreeElement<T> insert(T value, Comparator<T> comp) {
    if (value == null)
        throw new NullPointerException("null not supported");

    int cmp = comp.compare(value, info);
    if (cmp > 0) {
        // 新值更大，作为右子节点
        return new InnerNode<>(info, new Leaf<>(info), new Leaf<>(value));
    } else if (cmp < 0) {
        // 新值更小，作为左子节点
        return new InnerNode<>(info, new Leaf<>(value), new Leaf<>(info));
    }
    // 值已存在，返回自身
    return this;
}

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