高效能list转tree树形结构，扁平化线性复杂度

背景

最近在做业务的时候，发现有很多地方需要将数据库查询出来的list转为tree结构，基于面向对象的思想，想着做成一个通用的工具类，使用泛型，然后首先想到的是使用递归，O(n * n) 后面觉得递归的传统方式，时间复杂度过高，基于此进行优化，想到了一个线性规划的方式，进行数据扁平化转为线性复杂度O(N)

接口限定

定义一个ItreeNode接口，该接口主要用来子类实现，自己定义父节点的规则，只要使用方自己实现parent方法，自己定义父节点的规则，这样就无需id和parentId必须提前限制类型了， string或者对象都可以作为获取父节点的基准

import java.util.List;

/**
 * 通过实现该接口的子类 自己定义parent的规则
 * @param <T>
 */
public interface ITreeNode<T> {

    T parent();

    void setChildren(List<T> children);

    List<T> getChildren();
}

第一版

使用stream进行流式编程加上栈结构，不使用递归的方式，但是每个节点都得循环里面forEach找到关联的子节点

时间复杂度O(N*N)

 public static <T extends ITreeNode<T>> List<T> list2Tree1(Collection<T> source) {
        List<T> roots = source.stream().filter(node -> node.parent() == null).collect(Collectors.toList());
        Stack<T> rootStack = roots.stream().collect(Collectors.toCollection(Stack::new));
        while (!rootStack.isEmpty()) {
            T node = rootStack.pop();
            node.setChildren(
                    source.stream()
                    .filter(child -> Objects.equals(child.parent(), node))
                    .collect(Collectors.toList()));
            rootStack.addAll(node.getChildren());
        }
        return roots;
    }

这种方式当数据量大的时候，容易耗时，时间复杂度过高

第二版

使用线性规划，只需要提前将某个父节点的字节点关系映射缓存起来，后续直接通过父节点就能直接拿到子节点数据，只需要循环一次，时间复杂度变为线性O(N)

 public static <T extends ITreeNode<T>> List<T> list2Tree(Collection<T> source) {

        Map<T, List<T>> relationMap = new HashMap<>();
        source.forEach(node -> relationMap.computeIfAbsent(node.parent(), k -> new ArrayList<>()).add(node));

        List<T> roots = relationMap.getOrDefault(null, Collections.emptyList());
        Stack<T> rootStack = roots.stream().collect(Collectors.toCollection(Stack::new));

        while (!rootStack.isEmpty()) {
            T node = rootStack.pop();
            List<T> childList = relationMap.getOrDefault(node, Collections.emptyList());
            node.setChildren(childList);
            rootStack.addAll(node.getChildren());
        }
        return roots;
    }

测试

  public static void main(String[] args) {
        // List<TreeMember> list = new ArrayList<>();
//        list.add(new TreeMember(1,null,"广东"));
//        list.add(new TreeMember(2,1,"深圳"));
//        list.add(new TreeMember(3,2,"南山"));
//        list.add(new TreeMember(4,null,"广西"));
//        list.add(new TreeMember(5,2,"龙华"));
        //        List<TreeMember> tree = list2Tree(list);

        List<TreeMember2> list = new ArrayList<>();

        String guangdong = UUID.randomUUID().toString();
        String shenzhen = UUID.randomUUID().toString();
        String nanshan = UUID.randomUUID().toString();
        String guangxi = UUID.randomUUID().toString();

        list.add(new TreeMember2("广东", null, guangdong));
        list.add(new TreeMember2("深圳", guangdong, shenzhen));
        list.add(new TreeMember2("南山", shenzhen, nanshan));
        list.add(new TreeMember2("广西", null, guangxi));
        List<TreeMember2> tree = list2Tree(list);

        System.out.println("tree = " + tree);
    }

image.png