有这么样一个需求：将以下二维记录转成一个树型菜单

很明显，结果将是森林。

那么这里提供一个通用算法，来实现菜单的转换。

首先，将所有记录读入：

List<Department> departments = departmentMapper.selectAllDepartment();

其次，使用一个哈希表，将各部门id与部门实例进行映射：

Map<Integer,DepartmentTreeDto> departmentTreeDtoMap= new HashMap<>();

for (var i : departments){
    DepartmentTreeDto dto = new DepartmentTreeDto();
    dto.setDepartmentName(i.getDepartmentName());
    dto.setSubDepartment(new ArrayList<>());
    departmentTreeDtoMap.put(i.getDepartmentId(),dto);
}

因为我们需要对结果进行展示，所以需要这么样的一个数据传输对象：

public class DepartmentTreeDto extends Department {

    private Integer departmentId;

    private String departmentName;

    private Integer departmentPriority;

    private String departmentRemark;

    private List<DepartmentTreeDto> subDepartment;
}

最终结果都这么显示。

接下来，我们遍历departments，如果父部门不为空，那就从哈希表中找到其对应的父部门，并加入到其父部门的子部门列表中，反之如果该部门为顶级部门，那么久加入到一个存放最终结果的列表中：

List<DepartmentTreeDto> ret = new ArrayList<>();
        for (var i : departments){
            if (i.getParentDepartment() != null){
                DepartmentTreeDto parent = departmentTreeDtoMap.get(i.getParentDepartment());
                parent.getSubDepartment().add(departmentTreeDtoMap.get(i.getDepartmentId()));
            }else{
                ret.add(departmentTreeDtoMap.get(i.getDepartmentId()));
            }
        }

经过目测，结果正确：

该算法的时间复杂度为O(N)；

完整代码：

List<Department> departments = departmentMapper.selectAllDepartment();

        Map<Integer,DepartmentTreeDto> departmentTreeDtoMap= new HashMap<>();

        for (var i : departments){
            DepartmentTreeDto dto = new DepartmentTreeDto();
            dto.setDepartmentName(i.getDepartmentName());
            dto.setSubDepartment(new ArrayList<>());
            departmentTreeDtoMap.put(i.getDepartmentId(),dto);
        }


        List<DepartmentTreeDto> ret = new ArrayList<>();
        for (var i : departments){
            if (i.getParentDepartment() != null){
                DepartmentTreeDto parent = departmentTreeDtoMap.get(i.getParentDepartment());
                parent.getSubDepartment().add(departmentTreeDtoMap.get(i.getDepartmentId()));
            }else{
                ret.add(departmentTreeDtoMap.get(i.getDepartmentId()));
            }
        }