java - 如何将类别集合转换为树结构

Question

我正在使用 p:multiSelectListbox 做一个树选择器。我有一个类别集合，我尝试将类别转换为组件支持的结构(类别是无序的)。这是我的类别 bean:

public class Category {
    private String id;
    private String pid; //parentId
    private String name;
    private String value;

    //getter and setter
}

这是我的转换方法:

public List<SelectItem> tree(List<Category> categories) {
    Map<Category, SelectItem> map = new HashMap<>();

    for (Category node : categories) {
        //Check if current category is leaf node, if true new SelectItem, else new SelectItemGroup
        SelectItem item;
        if (categories.stream().noneMatch(n -> node.getId().equals(n.getPid()))) {
            item = new SelectItem(node.getValue(), node.getName());
        } else {
            item = new SelectItemGroup(node.getName());
        }
        map.put(node, item);
    }
    //the result return
    //items just add the root level, and child level add into it's parent level
    List<SelectItem> items = new ArrayList<>();

    categories.forEach(node -> {
        //get parent category of current's
        SelectItem item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid())).findFirst().orElse(null));

        //parent category is not exists, it's mean current category is root level
        if (item == null) {
            items.add(map.get(node)); //add root
        } else {
            SelectItemGroup parentGroup = (SelectItemGroup) item;
            SelectItem[] selectItems = parentGroup.getSelectItems();

            List<SelectItem> selectItemList = new ArrayList<>();
            if (selectItems != null) selectItemList.addAll(Arrays.asList(selectItems));
            //add current category into it's parent's children
            selectItemList.add(map.get(node));
            parentGroup.setSelectItems(selectItemList.toArray(new SelectItem[0]));
        }
    });

    return items;
}

当类别大小小于10000时，他的效果很好；如果大小大于20000，就会变得非常慢。有谁知道更有效的方法吗？

Answer 1

这些代码的时间复杂度为 O(n^2):

categories.forEach(node -> {//获取当前SelectItem的父类别 item = map.get(categories.stream().filter(n -> n.getId().equals(node.getPid) ())).findFirst().orElse(null))

使用 HashMap 根据 pid&id 关系从类别列表创建树结构，时间复杂度为 O(n)。基本思想如下所述。

1. 遍历类别列表，并将pid&id映射放入HashMap，时间复杂度:O(n)。在 map 中，我们将(pid:List of Children ids) 作为Map.Entity。现在我们实际上已经有了树结构。

2. 接下来我们要做的是遍历通过 hashmap 演示的树，并得到结果。这可以通过 @Ken Bekov 给出的递归方式或使用迭代方式来完成。遍历过程也需要O(n)时间。

所以整个解决方案的时间复杂度是O(n)。当 n 较大时，例如 20000，它应该比原始解决方案快得多。