Java实现：从扁平Customers列表构建层级结构（求优化方案）

核心思路 #

这是个非常典型的扁平数据转层级结构的需求，要做到高效转换，核心就是避免重复遍历列表查找父节点——那种方式时间复杂度是O(n²)，数据量大的时候性能会拉胯。我们可以用哈希表（Java里的HashMap）先把所有节点按id做映射，这样后续找父节点的操作能直接降到O(1)，整体时间复杂度优化到O(n)，属于用空间换时间的经典高效思路。

实现步骤 #

1. 构建节点映射表：遍历一次扁平列表，把每个Customer对象以自身id为key存入哈希表，这样后续能通过父节点的parentId直接定位到父对象。
2. 关联父子节点：再次遍历扁平列表，根据每个节点的parentId，从哈希表中取出对应的父节点，把当前节点添加到父节点的children集合里。
3. 收集根节点：最后筛选出所有parentId = 0的节点，这些就是层级结构的顶层节点。

代码实现 #

首先是Customers类的定义（按问题描述还原）：

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

    // 构造函数
    public Customers(int id, String name, int parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }

    // 必备的getter方法
    public int getId() { return id; }
    public int getParentId() { return parentId; }
    public List<Customers> getChildren() { return children; }
    public String getName() { return name; }
}

然后是Application类中hierarchicalList方法的实现：

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

public class Application {

    public static List<Customers> hierarchicalList(List<Customers> flatCustomers) {
        // 1. 先把所有节点存入哈希表，方便快速查找
        Map<Integer, Customers> customerMap = new HashMap<>();
        for (Customers customer : flatCustomers) {
            customerMap.put(customer.getId(), customer);
        }

        // 2. 关联父子关系，同时收集根节点
        List<Customers> rootNodes = new ArrayList<>();
        for (Customers customer : flatCustomers) {
            int parentId = customer.getParentId();
            if (parentId == 0) {
                // parentId为0是根节点，直接加入顶层列表
                rootNodes.add(customer);
            } else {
                // 从哈希表取出父节点，把当前节点加入父节点的子列表
                Customers parent = customerMap.get(parentId);
                if (parent != null) { // 兼容无效parentId的情况，避免空指针
                    parent.getChildren().add(customer);
                }
            }
        }

        return rootNodes;
    }

    // 测试用例代码
    public static void main(String[] args) {
        // 模拟无序的扁平输入列表
        List<Customers> flatList = new ArrayList<>();
        flatList.add(new Customers(1, "Customer A", 0));
        flatList.add(new Customers(3, "Customer C", 1));
        flatList.add(new Customers(2, "Customer B", 1));
        flatList.add(new Customers(4, "Customer D", 3));
        flatList.add(new Customers(5, "Customer E", 0));

        // 转换为层级结构
        List<Customers> hierarchicalResult = hierarchicalList(flatList);

        // 递归打印层级结构验证结果
        printHierarchy(hierarchicalResult, 0);
    }

    // 辅助递归打印方法
    private static void printHierarchy(List<Customers> customers, int depth) {
        String indent = "  ".repeat(depth);
        for (Customers customer : customers) {
            System.out.printf("%s%s (id: %d)%n", indent, customer.getName(), customer.getId());
            printHierarchy(customer.getChildren(), depth + 1);
        }
    }
}

预期输出 #

运行测试代码后，会得到符合预期的层级结构输出：

Customer A (id: 1)
  Customer C (id: 3)
    Customer D (id: 4)
  Customer B (id: 2)
Customer E (id: 5)

方案优势 #

• 性能最优：仅需两次线性遍历，时间复杂度O(n)，数据量越大，对比O(n²)的实现优势越明显。
• 逻辑清晰：分步骤处理，代码可读性高，后续维护成本低。
• 鲁棒性强：加入了无效parentId的判断，避免空指针异常。

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