private IndicatorTreeDTO generateIndicatorTree(List<IndicatorTreeDTO> indicatorTreeDTOList) {
// 创建ID到IndicatorTreeDTO的映射
Map<String, IndicatorTreeDTO> idMap = new HashMap<>();
// 创建parentId到children的映射
Map<String, List<IndicatorTreeDTO>> parentIdMap = new HashMap<>();
// 使用一次forEach填充两个映射
indicatorTreeDTOList.forEach(indicator -> {
idMap.put(indicator.getId(), indicator);
// 防止自我引用
if (isChildren(indicator)) {
parentIdMap.computeIfAbsent(indicator.getParent_id(), k -> new ArrayList<>()).add(indicator);
}
});
// 顶点节点列表
List<IndicatorTreeDTO> topChildren = new ArrayList<>();
parentIdMap.forEach((parentId, children) -> {
// 拿IndicatorTreeDTO的parent_id id 来组装树, 如果parent_id找不到 说明是第一层
IndicatorTreeDTO parent = idMap.get(parentId);
if (parent != null) {
parent.setChildren(children);
} else {
topChildren.addAll(children);
}
});
IndicatorTreeDTO indicatorTreeDTO = new IndicatorTreeDTO();
indicatorTreeDTO.setChildren(topChildren);
return indicatorTreeDTO;
}
private boolean isChildren(IndicatorTreeDTO indicator) {
return indicator.getParent_id() != null && !indicator.getId().equals(indicator.getParent_id());
}
在当前的实现中,我们已经处理了:
使用了深度优先搜索(DFS)来检测图中是否存在环
private boolean detectCycle(Map<String, List<IndicatorTreeDTO>> childrenMap, String nodeId, Set<String> visited, Set<String> recStack) {
if (recStack.contains(nodeId)) {
return true;
}
if (visited.contains(nodeId)) {
return false;
}
visited.add(nodeId);
recStack.add(nodeId);
List<IndicatorTreeDTO> children = childrenMap.get(nodeId);
if (children != null) {
for (IndicatorTreeDTO child : children) {
if (detectCycle(childrenMap, child.getId(), visited, recStack)) {
return true;
}
}
}
recStack.remove(nodeId);
return false;
}
private IndicatorTreeDTO generateIndicatorTree(List<IndicatorTreeDTO> indicatorTreeDTOList) {
Map<String, IndicatorTreeDTO> idMap = new HashMap<>();
Map<String, List<IndicatorTreeDTO>> parentIdMap = new HashMap<>();
indicatorTreeDTOList.forEach(indicator -> {
idMap.put(indicator.getId(), indicator);
parentIdMap.computeIfAbsent(indicator.getParent_id(), k -> new ArrayList<>()).add(indicator);
});
// 重新构建树之前检查
Set<String> visited = new HashSet<>();
Set<String> recStack = new HashSet<>();
for (IndicatorTreeDTO node : indicatorTreeDTOList) {
if (detectCycle(parentIdMap, node.getId(), visited, recStack)) {
throw new IllegalArgumentException(String.format("Circular reference detected with id: %s", node.getId()));
}
}
..........
}