HashMap为何丢失部分值？二叉树垂直遍历代码问题排查

测试树输入为root = [3,9,20,null,null,15,7]，目标是构建列号（水平深度）到对应节点列表的Map时，第一段代码输出异常[[],[15],[],[]]，第二段代码得到预期结果[[9],[3,15],[20],[7]]，核心原因是第一段代码复用了同一个List实例，导致Map中所有列指向的是同一个列表的引用。

错误代码的典型问题场景 #

第一段代码大概率是类似以下的实现：

List<Integer> temp = new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>();

void dfs(TreeNode node, int col) {
    if (node == null) return;
    temp.add(node.val);
    map.put(col, temp); // 所有列都存入同一个temp的引用
    dfs(node.left, col - 1);
    temp.remove(temp.size() - 1); // 回溯时移除元素，会修改所有列对应的列表
    dfs(node.right, col + 1);
    temp.remove(temp.size() - 1);
}

这里的关键问题：

• Map中所有列对应的列表，实际上都是temp这同一个对象的引用
• 递归回溯时执行的remove操作，会直接修改这个唯一的List实例，导致之前存入Map的所有列的列表都被同步修改
• 最终只有最后访问的节点（比如示例中的15）所在列的列表残留值，其他列的列表都被回溯清空

正确代码的核心改进 #

第二段代码解决问题的关键是为每个列维护独立的List实例，典型实现如下：

Map<Integer, List<Integer>> map = new HashMap<>();

void dfs(TreeNode node, int col) {
    if (node == null) return;
    // 为不存在的列创建新的ArrayList，每个列的列表都是独立对象
    map.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);
    dfs(node.left, col - 1);
    dfs(node.right, col + 1);
}

这里通过computeIfAbsent确保每个列都有专属的List实例，不存在引用共享的问题，回溯操作（如果有）只会影响当前递归栈中的临时操作，不会干扰其他列的列表内容。

总结 #

第一段代码失效的本质是引用复用导致的副作用：Map中存储的不是独立的列表，而是同一个List对象的引用，后续的修改操作会同步影响所有列对应的列表；第二段代码通过为每个列创建独立List实例，彻底避免了这个问题。

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