理解Java引用机制：二叉搜索树BST的addNode函数行为异常问题

你的猜测完全正确，这个问题本质就是Java的值传递特性导致的。

核心规则铺垫 #

Java中所有参数传递都是值传递：

• 对于基础类型，传递的是值的副本，修改参数不影响外部变量
• 对于引用类型，传递的是引用的内存地址的副本，不是原引用本身。方法内的参数和外部的原引用指向同一个堆对象，但如果直接给参数变量赋值新对象，修改的只是副本的指向，完全不会影响外部原引用的指向。

第一个void版本失效原因 #

public static void addToTree(Node n, int value){ //return type is void
    if (n != null){
        if (n.val >= value){
            addToTree(n.left, value);
        } else { 
            addToTree(n.right, value);
        }
    } else {
        n = new Node(value);
    }
}

当递归到子节点为null的场景时：

1. 你传入的n.left/n.right本身是null，方法接收到的参数n是一个指向null的引用副本
2. 你在else分支执行n = new Node(value)，只是把方法内部的这个局部副本指向了新创建的Node对象
3. 方法执行结束后局部变量销毁，父节点的left/right属性还是原来的null，新节点根本没有挂载到树上，所以整个插入逻辑无效。

第二个带返回值版本生效原因 #

public static Node addToTree(Node n, int value){ //return type is Node
    if (n != null){
        if (n.val >= value){
            n.left = addToTree(n.left, value); //sets n.left with the return value
        } else { 
            n.right = addToTree(n.right, value); //sets n.right with the return value
        }
    } else {
        n = new Node(value);
        return n; //returns the new node after creating (adding) it
    }
    return n;
}

这个版本通过返回值+主动赋值解决了值传递的问题：

1. 当子节点为null时，新创建的节点会作为返回值传回上层调用
2. 上层调用主动执行n.left = 返回值/n.right = 返回值，相当于直接修改父节点的属性，把新节点正确挂到了树上
3. 对于非null的节点，返回原节点本身，赋值操作不会改变原有结构，不影响逻辑。

极简对照示例 #

这个问题和下面这段代码的原理完全一致：

public static void test(String s) {
    s = "新字符串";
}
// 外部调用
String a = "旧字符串";
test(a);
System.out.println(a); // 输出还是"旧字符串"，因为修改的只是参数副本的指向

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