Java递归实现BST插入失败求助：空树插入后根节点未更新

核心问题：Java的传参机制 #

Java是值传递，哪怕是对象类型，传递的也是对象引用的「副本」。你的代码存在两个关键问题：

• 调用tree_insert(tree.root, 1)时，tree.root是null，这个null的副本被传给方法参数x。方法里执行x = new Node(k)，只是把这个副本引用指向了新创建的Node，完全不会影响外部的tree.root。
• 递归调用tree_insert(x.left, k)时，传递的是x.left当前值的副本，就算方法里给副本赋值新Node，x.left本身也不会被修改。

修正方案 #

方案1：让方法返回Node，通过返回值更新节点引用

修改方法为返回Node类型，每次递归返回修改后的节点，上层调用时把返回值赋值给对应的left/right（包括根节点）：

public Node treeInsert(Node x, int k) {
    if (x == null) {
        return new Node(k);
    }
    if (k < x.val) {
        x.left = treeInsert(x.left, k);
    } else {
        x.right = treeInsert(x.right, k);
    }
    return x;
}

调用时需要把返回值赋值给根节点：

tree.root = treeInsert(tree.root, 1);

方案2：封装递归逻辑，直接操作树的根成员变量

把对外暴露的方法改成无需传递节点参数，内部用递归辅助方法处理，直接更新树的root成员：

// 对外调用的方法
public void treeInsert(int k) {
    root = insertHelper(root, k);
}

// 递归辅助方法（私有）
private Node insertHelper(Node x, int k) {
    if (x == null) {
        return new Node(k);
    }
    if (k < x.val) {
        x.left = insertHelper(x.left, k);
    } else {
        x.right = insertHelper(x.right, k);
    }
    return x;
}

调用时直接执行：

tree.treeInsert(1);

和C++的区别 #

你之前用C++实现时，应该是用了指针的引用（比如Node* &x），这种方式可以在函数内部直接修改外部指针的指向。但Java没有这种语法，只能通过返回值或者直接操作类成员变量来达到同样的效果。

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