java从给定的HashMap构造树

Question

我想遍历一个HashMap<Integer, ArrayList<Integer>> map并从这个映射构建一棵树。例如，我有以下映射：1=[2,3]，2=[3,4]，3=[1,5]，4=[2,5]，5=[1,4]。我要做的是以以下方式遍历此地图：

public static Tree getTree (HashMap<Integer, ArrayList<Integer>> paths) {

    Tree<Integer> tree = new Tree(-1);
    Integer node;

    for (int i = 1; i <= paths.size(); i++) {

        for (int j = 0; j < paths.get(i).size(); j++) {

            node = paths.get(i).get(j);
            tree.addLeaf(i, node);

            for(int k = 0; k < paths.get(node).size(); k++) {

                tree.addLeaf(node, paths.get(node).get(k));
                node = paths.get(node).get(k);

                // now I have to go to paths.get(node) and receive its ArrayList

                for (int t = 0; t < paths.get(node).size(); t++) {

                      tree.addLeaf(node, paths.get(node).get(t));
                      node = paths.get(node).get(t);


                }

            }
        }
    }

    return tree;
}

如果新节点等于其一个祖先节点，则应将该节点添加到树中，但不应再进行遍历。我想动态执行此操作

Answer 1

使用递归遍历映射，将当前状态作为参数传递给递归方法：

public void step(Map<Integer, List<Integer>> tree, List<Integer> nodes, Integer key) {
    if (nodes.contains(key)) {
        // skip node which we already processed
        return;
    }
    nodes.add(key);

    List<Integer> children = tree.get(key);
    // add sanity checks here if you expect inconsistent data
    for (Integer child : children) {
        step(tree, nodes, child);
    }
}

现在这里最难的部分是找到哪个节点是根节点。由于使用映射，所以映射条目没有顺序。所以我把这部分留给你们：

step(map, tempList, 1);