BST insert（root，value）递归方法

Question

我正在从事BST算法的作业分配，而我无可救药地停留在insert方法上。我在网上找到的所有资源的版本都与我创建的版本相似，但是我的教授通过的JUnit测试未能通过。我可以传递基本情况（空根和二叉树，其中root.payload ==值）。我似乎无法通过下一个测试。这是我的insert（root，value）方法的代码：

public static Node<Integer> insert(Node<Integer> root, Integer value) {
    if (root == null) {
        root = new BinaryNode<>(value);
    } else if (root.payload.equals(value)) {
        return root;
    } else if (value < root.payload) {
        return root.left = insert(root.left, value);
    } else {
        return root.right = insert(root.right, value);
    }
    return root;
}

最终返回的是原始根节点，但是根据我的理解，最后返回的值应该是我的新节点。我已经看过我的教科书和一些在线资源，并且所有资源都与该设计非常相似，因此我对为什么它不起作用感到困惑。我尝试了其他一些设计，但最终所有设计都是NullPointerException。提供给我们的JUnit测试除了检查节点的有效负载外，还验证我们是否将该节点插入了正确的位置。我都没有通过这两项测试。这是我们使用递归的第一个任务，因此我仍然很陌生。任何指导将不胜感激！

Answer 1

如果您希望方法返回的值是新插入的节点，则还必须在elseIf子句中添加return语句，以便在递归堆栈展开时它会返回新创建的节点。检查下面的代码

public static Node<Integer> insert(Node<Integer> root, Integer value) {
if (root == null) {
    root = new Node<>(value);
} else if (value <= root.payload) {
    return root.left = insert(root.left, value);   // add a return here
} else {
   return  root.right = insert(root.right, value);  // add a return here
}
return root;

}