Java中Map.Entry作为参数传递时子方法修改未同步至父方法的原因

我在实现LeetCode《最深叶节点和》问题的DFS递归解法时，用Map.Entry<Integer, Integer>存储最深层级及其对应节点值的和，遇到了一个传参相关的问题：

• 把Map.Entry声明为类全局变量时，子方法对它的修改（包括重新赋值新对象）能正确同步到父方法；
• 但在父方法初始化后将其作为参数传递给DFS子方法时，子方法里重新赋值新Entry的操作无法反映到父方法，只有setValue()修改内部值的操作有效。

有效代码 #

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    Map.Entry<Integer, Integer> deepestLevelSum; 

    public int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        deepestLevelSum = null;
        dfsHelper(root, 0);
        return deepestLevelSum.getValue();
    }

    private void dfsHelper(TreeNode root, int level){
        if (root.left == null && root.right == null) {
            if (deepestLevelSum == null || deepestLevelSum.getKey() < level) {
                deepestLevelSum = new HashMap.SimpleEntry(level, root.val);     
            } else if (deepestLevelSum.getKey() == level){
                deepestLevelSum.setValue(deepestLevelSum.getValue()+root.val);
            }
        } else {
            if (root.left != null) 
                dfsHelper(root.left, level+1);
            if (root.right != null)
                dfsHelper(root.right, level+1);
        }
    }
}

无效代码 #

class Solution {

    public int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        Map.Entry<Integer, Integer> deepestLevelSum = new HashMap.SimpleEntry(0, root.val); 
        dfsHelper(root, 0, deepestLevelSum);
        return deepestLevelSum.getValue();
    }

    private void dfsHelper(TreeNode root, int level, Map.Entry<Integer, Integer> deepestLevelSum){
        if (root.left == null && root.right == null) {
            if (deepestLevelSum == null || deepestLevelSum.getKey() < level) {
                // 这里的赋值只修改了子方法的局部引用，父方法的引用不受影响
                deepestLevelSum = new HashMap.SimpleEntry(level, root.val);     
            } else if (deepestLevelSum.getKey() == level){
                // 这里修改的是原对象的内部值，父方法能看到变化
                deepestLevelSum.setValue(deepestLevelSum.getValue()+root.val);
            }
        } else {
            if (root.left != null) 
                dfsHelper(root.left, level+1, deepestLevelSum);
            if (root.right != null)
                dfsHelper(root.right, level+1, deepestLevelSum);
        }
    }
}

问题根源：Java的传参机制是值传递 #

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

1. 当传递对象时，传递的是对象引用的副本，而不是引用本身。父方法和子方法的deepestLevelSum是两个独立的引用变量，只是一开始指向同一个Map.Entry对象。
2. 子方法中调用setValue()时，是通过引用副本操作原对象的内部数据，所以父方法的引用指向的还是同一个对象，能看到修改后的结果。
3. 但当子方法执行deepestLevelSum = new HashMap.SimpleEntry(...)时，是给子方法自己的局部引用变量重新赋值了一个新对象，父方法的引用变量仍然指向原来的对象，自然看不到这个新对象的存在。

而全局变量的情况是，父方法和子方法共享同一个引用变量，不管是修改对象内部值还是重新赋值引用，都会直接作用在这个共享变量上，所以父方法能同步看到变化。

修正方案 #

如果不想用全局变量，可以用一个包装类来持有Map.Entry，因为包装类是对象，传递的是包装类引用的副本，修改包装类内部的Entry引用会反映到父方法：

class Solution {
    // 自定义简单的Holder类
    static class EntryHolder {
        Map.Entry<Integer, Integer> entry;
    }

    public int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        EntryHolder holder = new EntryHolder();
        holder.entry = new HashMap.SimpleEntry(0, root.val);
        dfsHelper(root, 0, holder);
        return holder.entry.getValue();
    }

    private void dfsHelper(TreeNode root, int level, EntryHolder holder){
        if (root.left == null && root.right == null) {
            if (holder.entry == null || holder.entry.getKey() < level) {
                // 修改Holder内部的entry引用，父方法的Holder对象能看到这个变化
                holder.entry = new HashMap.SimpleEntry(level, root.val);     
            } else if (holder.entry.getKey() == level){
                holder.entry.setValue(holder.entry.getValue()+root.val);
            }
        } else {
            if (root.left != null) 
                dfsHelper(root.left, level+1, holder);
            if (root.right != null)
                dfsHelper(root.right, level+1, holder);
        }
    }
}

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