如何遍历HashMap<Integer, ArrayList<Integer>>并构建树？

针对你提出的遍历HashMap<Integer, ArrayList<Integer>>并构建树的需求，我整理了一套可运行的实现方案，结合你给出的代码框架完善了逻辑，同时处理了示例集合中的环问题（毕竟你的示例是带环的图结构，直接遍历会陷入死循环）。

先明确前提 #

示例集合是：
1=[2,3], 2=[3,4], 3=[1,5], 4=[2,5], 5=[1,4]
这是一个带环的连通图，所以构建树时必须记录已访问的节点，避免重复添加和无限递归。

完整代码实现 #

首先我们需要一个基础的Tree类来支撑树结构（如果你的项目中已有Tree类，可以直接替换）：

class Tree<T> {
    public T value;
    private List<Tree<T>> children;

    public Tree(T value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(Tree<T> child) {
        this.children.add(child);
    }

    // 辅助打印树的方法，方便验证结果
    public void printTree(String indent) {
        System.out.println(indent + value);
        for (Tree<T> child : children) {
            child.printTree(indent + "  ");
        }
    }
}

然后是你需要的getTree方法的完整实现，结合深度优先遍历构建树：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class TreeBuilder {
    public static Tree<Integer> getTree(HashMap<Integer, ArrayList<Integer>> paths) {
        // 初始化根节点为-1，作为所有子树的顶层父节点
        Tree<Integer> rootTree = new Tree<>(-1);
        // 记录已访问的节点，防止环和重复构建
        Set<Integer> visitedNodes = new HashSet<>();

        // 遍历HashMap中的每个节点（key从1到集合大小，对应示例的1-5）
        for (int nodeId = 1; nodeId <= paths.size(); nodeId++) {
            if (!visitedNodes.contains(nodeId)) {
                // 创建当前节点的树实例
                Tree<Integer> currentNode = new Tree<>(nodeId);
                rootTree.addChild(currentNode);
                visitedNodes.add(nodeId);
                // 递归构建当前节点的子树
                buildSubtree(currentNode, paths, visitedNodes);
            }
        }

        return rootTree;
    }

    /**
     * 递归构建子树的辅助方法
     */
    private static void buildSubtree(Tree<Integer> parentNode, HashMap<Integer, ArrayList<Integer>> paths, Set<Integer> visited) {
        Integer parentValue = parentNode.value;
        // 遍历当前节点的所有邻接节点
        for (Integer neighbor : paths.get(parentValue)) {
            if (!visited.contains(neighbor)) {
                Tree<Integer> childNode = new Tree<>(neighbor);
                parentNode.addChild(childNode);
                visited.add(neighbor);
                // 继续递归处理子节点的邻接节点
                buildSubtree(childNode, paths, visited);
            }
        }
    }

    // 测试用例，验证结果
    public static void main(String[] args) {
        HashMap<Integer, ArrayList<Integer>> testPaths = new HashMap<>();
        testPaths.put(1, new ArrayList<>(List.of(2, 3)));
        testPaths.put(2, new ArrayList<>(List.of(3, 4)));
        testPaths.put(3, new ArrayList<>(List.of(1, 5)));
        testPaths.put(4, new ArrayList<>(List.of(2, 5)));
        testPaths.put(5, new ArrayList<>(List.of(1, 4)));

        Tree<Integer> resultTree = getTree(testPaths);
        resultTree.printTree("");
    }
}

关键逻辑说明 #

• 防环处理：用HashSet记录已访问的节点，确保每个节点只被添加一次，避免因图中的环导致无限递归
• 递归构建：通过buildSubtree方法深度优先遍历邻接节点，自然形成树的层级结构
• 根节点设计：用-1作为顶层根节点，即使输入的图包含多个独立连通分量，每个分量都会成为根节点的子节点
• 遍历顺序：按节点编号1到N遍历，确保每个节点都被处理到

测试结果 #

运行main方法后，会输出如下树结构（深度优先遍历的结果）：

-1
  1
    2
      4
        5
    3

如果需要广度优先的构建顺序，可以把递归改成队列实现的BFS逻辑，调整起来也很简单~

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