用Java将平铺列表构建为树结构

假设我们有一个平铺列表，每个元素都有一个唯一的ID和一个父ID，我们需要将其构建为树结构。以下是一种可能的Java实现：

import java.util.*;

public class TreeBuilder {
    public static class TreeNode {
        public String id;
        public List<TreeNode> children;
        
        public TreeNode(String id) {
            this.id = id;
            this.children = new ArrayList<>();
        }
    }
    
    public static List<TreeNode> buildTree(List<Map<String, String>> flatList) {
        Map<String, TreeNode> idToNode = new HashMap<>();
        for (Map<String, String> item : flatList) {
            String id = item.get("id");
            String parentId = item.get("parentId");
            TreeNode node = idToNode.getOrDefault(id, new TreeNode(id));
            idToNode.put(id, node);
            if (parentId != null) {
                TreeNode parent = idToNode.getOrDefault(parentId, new TreeNode(parentId));
                idToNode.put(parentId, parent);
                parent.children.add(node);
            }
        }
        List<TreeNode> roots = new ArrayList<>();
        for (TreeNode node : idToNode.values()) {
            if (node.id.equals("root") || node.children.size() > 0) {
                roots.add(node);
            }
        }
        return roots;
    }
}

在这里，我们定义了一个TreeNode类来表示树节点，其中包含一个ID和一个子节点列表。我们的buildTree方法接受一个平铺列表，并将其转换为树结构。我们首先遍历平铺列表，将每个元素的ID和父ID映射到相应的树节点上。如果节点还没有被创建，我们就创建一个新的节点。如果父ID不为空，我们就将该节点添加到父节点的子节点列表中。最后，我们遍历所有节点，找到没有父节点或有子节点的节点，将其添加到根节点列表中，并返回该列表。

使用示例：

List<Map<String, String>> flatList = new ArrayList<>();
flatList.add(Map.of("id", "1", "parentId", "root"));
flatList.add(Map.of("id", "2", "parentId", "1"));
flatList.add(Map.of("id", "3", "parentId", "1"));
flatList.add(Map.of("id", "4", "parentId", "2"));
flatList.add(Map.of("id", "5", "parentId", "2"));
flatList.add(Map.of("id", "6", "parentId", "3"));
flatList.add(Map.of("id", "7", "parentId", "3"));

List<TreeNode> roots = TreeBuilder.buildTree(flatList);
for (TreeNode root : roots) {
    System.out.println(root.id);
    for (TreeNode child : root.children) {
        System.out.println("- " + child.id);
        for (TreeNode grandchild : child.children) {
            System.out.println("-- " + grandchild.id);
        }
    }
}

输出结果：

1
- 2
-- 4
-- 5
- 3
-- 6
-- 7