关于Java值传递与二叉树修剪代码失效的疑问

问题背景 #

在解决二叉树修剪问题时，遇到两种递归实现的行为差异：直接递归的方案能正确修改原树结构，但调用辅助方法的方案无法生效。已知Java是值传递，传递对象时传递的是引用值，可修改对象内容，但疑惑为何将对象设为null时无法改变原树；同时测试案例中root和root2的left.left都变为null，对这种行为差异存在困惑。

代码示例 #

成功的解决方案 #

public TreeNode pruneTree(TreeNode root) {
    if (root == null)
        return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.val == 0 && root.left == null && root.right == null)
        root = null;
    else
        return root;
    return root;
}

失效的解决方案 #

public TreeNode pruneTree(TreeNode root) {
    pruneTree1(root);
    return root;
}

TreeNode pruneTree1 (TreeNode root) {
    if(root ==null)
        return root ;
    root.left = pruneTree1(root.left);
    root.right = pruneTree1(root.right);
    if(root.left==null && root.right==null && root.val==0) {
        System.out.println(root.val);
        root =null;
    }
    return root;
}

测试案例代码 #

public void run1() {
        TreeNode root = new TreeNode();
        root.val = 2;
        TreeNode left = new TreeNode();
        left.val = 3;
        TreeNode right = new TreeNode();
        right.val = 4;
        TreeNode leftLeft = new TreeNode();
        leftLeft.val = 5;
        TreeNode rightRight = new TreeNode();
        rightRight.val = 6;
        root.left = left;
        root.right = right;
        left.left = leftLeft;
        right.right = rightRight;
        System.out.println(root.left.left.val);
        TreeNode root2 = makeNull(root);
        System.out.println(root.left.left);
        System.out.println(root2.left.left);

    };

 public   TreeNode  makeNull (TreeNode root){
        if(root ==null)
            return root ;
        root.left = makeNull(root.left);
        root.right = makeNull(root.right);
        if(root.val==5)
            root=null;
        return root;
    }

行为差异解析 #

成功方案的核心逻辑 #

该方案的关键在于递归返回修剪后的节点，并将返回值重新赋值给父节点的left/right指针：

• 递归处理左右子树时，root.left = pruneTree(root.left)会将子树修剪后的结果（可能是null）赋值给当前节点的左指针，直接修改了原树的结构。
• 当当前节点需要被修剪（值为0且左右子树为空），将root设为null并返回，上层调用会用这个null更新父节点的对应指针，从而把该节点从树中移除。

失效方案的问题所在 #

辅助方法pruneTree1虽然执行了相同的递归逻辑并返回了修剪后的节点，但主方法pruneTree没有接收这个返回值来更新原root指针：

• Java是值传递，传递给pruneTree1的root是原引用的副本。在方法内部将root = null，只是修改了这个局部副本的指向，并不会改变原树中父节点指向该节点的指针。
• 虽然递归中对root.left和root.right做了赋值，子树的修剪是生效的，但如果原root本身需要被修剪（比如整棵树只有一个值为0的节点），主方法返回的还是原来的root引用，导致修剪失败。

测试案例的行为解释 #

测试案例中root和root2的left.left都变为null，原因在于：

• 在makeNull方法中，处理val=5的节点时，将局部变量root设为null并返回。而调用root.left = makeNull(root.left)时，这个返回的null被赋值给了root.left，也就是原树中left.left的指针被更新为null。
• root2是makeNull(root)的返回值，makeNull处理根节点时，根节点的val不是5，所以返回原根节点引用，但此时根节点的left.left已经被修改为null，因此root和root2的left.left都是null。

总结 #

Java中对象的传递是值传递，传递的是对象引用的副本：

• 如果要修改树的结构，必须通过将递归返回的结果赋值给父节点的指针来实现，这样才能更新原树的引用关系。
• 单纯在方法内部将局部引用变量设为null，只会改变局部变量的指向，不会影响原树中父节点的指针，因此无法修改原树结构。

内容的提问来源于stack exchange，提问作者Aman Kumar Sinha