方式一：Stream分组

使用stream分组子节点，再连接父子节点，最后返回根节点集合。2*n时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//1.原始列表数据
List<Node> nodes = 。。。

//2.将数结构的【子节点】全部选出来，并根据子节点的 【父id】 分组，返回Map。（key:父id,value：子节点集合）
Map<String, List<Node>> childNodes = CollectionUtils.convertMultiMap(
        CollectionUtils.filterList(nodes, r -> StringUtils.isNotBlank(r.getParentId())),
        Node::getParentId);

//3.连接父子节点
for (Node node : nodes) {
    node.setChildren(childNodes.get(node.getId()));
}

//4.返回根节点列表
return CollectionUtils.filterList(nodes,r -> StringUtils.isBlank(r.getParentId()));

public class CollectionUtils {
	/**
     * 应用 keyFunc 将集合转换为 Map<K,List<V>>集合
     */
    public static <K,V> Map<K,List<V>> convertMultiMap(Collection<V> from,Function<V,K> keyFunc){
        if (CollUtil.isEmpty(from)) {
            return new HashMap<>();
        }
        return from.stream().collect(Collectors.groupingBy(keyFunc,Collectors.mapping(Function.identity(),Collectors.toList())));
    }

	public static <T> List<T> filterList(Collection<T> from, Predicate<T> predicate) {
        if (CollUtil.isEmpty(from)) {
            return new ArrayList<>();
        }
        return from.stream().filter(predicate).collect(Collectors.toList());
    }
}

方式二：Stream双重遍历

n^2时间复杂度

1
2
3
4
5
6
7
//1.原始列表数据
List<Node> nodes = new ArrayList<>();
//2.返回根节点列表
List<Node> roots = nodes.stream().filter(father -> {
    father.children = nodes.stream().filter(child -> Objects.equals(father.id,child.parentId)).collect(Collectors.toList());
    return StringUtils.isBlank(father.getParentId());
}).collect(Collectors.toList());