如何在Java中利用parent_id从扁平列表构建树形结构？

嵌套循环的实现方式时间复杂度为O(n²)，当节点数量较多时性能会明显下降。用HashMap存储节点映射是最优方案，可以将整体时间复杂度降到O(n)，因为HashMap的查找操作是O(1)级别的。

实现思路 #

• 构建节点映射表：将所有节点存入HashMap<Long, Node>，key为节点的id，value为节点对象。后续查找父节点时可直接通过id快速定位。
• 关联父子节点并收集根节点：遍历所有节点，区分根节点与子节点：
  • 若节点的parentId为null，则该节点是根节点，加入根节点列表
  • 若节点的parentId不为null，则从HashMap中取出对应的父节点，将当前节点添加到父节点的children集合中
• 树形结构打印：递归遍历根节点及其子节点，根据层级添加缩进和分支符号，实现格式化输出。

完整代码实现 #

Node类（补充getName方法用于打印）

import java.util.ArrayList;
import java.util.List;

public class Node {
    private Long id;
    private String name;
    private Long parentId;
    private List<Node> children = new ArrayList<>();

    public Node(Long id, String name, Long parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }

    public Long getId() {
        return id;
    }

    public Long getParentId() {
        return parentId;
    }

    public List<Node> getChildren() {
        return children;
    }

    public String getName() {
        return name;
    }
}

树形构建与打印工具类

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreeBuilder {

    public static List<Node> buildTree(List<Node> flatNodes) {
        Map<Long, Node> nodeMap = new HashMap<>();
        List<Node> rootNodes = new ArrayList<>();

        // 构建节点映射表
        for (Node node : flatNodes) {
            nodeMap.put(node.getId(), node);
        }

        // 关联父子节点，收集根节点
        for (Node node : flatNodes) {
            Long parentId = node.getParentId();
            if (parentId == null) {
                rootNodes.add(node);
            } else {
                Node parentNode = nodeMap.get(parentId);
                if (parentNode != null) {
                    parentNode.getChildren().add(node);
                }
            }
        }

        return rootNodes;
    }

    // 打印树形结构
    public static void printTree(List<Node> rootNodes) {
        for (Node root : rootNodes) {
            printNode(root, "", true);
        }
    }

    private static void printNode(Node node, String prefix, boolean isLast) {
        System.out.println(prefix + (isLast ? "" : "├─ ") + node.getName());
        List<Node> children = node.getChildren();
        for (int i = 0; i < children.size(); i++) {
            boolean lastChild = (i == children.size() - 1);
            String newPrefix = prefix + (isLast ? "  " : "│ ");
            // 空行分隔匹配示例格式
            System.out.println(newPrefix);
            printNode(children.get(i), newPrefix + (lastChild ? "   " : "│  "), lastChild);
        }
    }

    public static void main(String[] args) {
        // 构造示例输入
        List<Node> flatNodes = new ArrayList<>();
        flatNodes.add(new Node(1L, "Assets", null));
        flatNodes.add(new Node(2L, "Current Assets", 1L));
        flatNodes.add(new Node(3L, "Cash", 2L));

        // 构建树形结构
        List<Node> treeRoots = buildTree(flatNodes);

        // 打印树形
        printTree(treeRoots);
    }
}

运行输出 #

Assets
  
   └── Current Assets
  
        └── Cash

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