1、前言

在开发的过程中很多业务场景需要一个树形结构的结果集进行前端展示，也可以理解为是一个无限父子结构。而实现方式也是有很多种，我这里提供递归和非递归两种实现方法吧。依赖引入了lombok

2、递归构建树结构

树结构基类，有需要构建树结构的类就继承

@Data
public class TreeNode {

    /**
     * 节点id
     */
    private Integer id;
    /**
     * 节点名称
     */
    private String name;
    /**
     *  父节点id
     */
    private Integer parentId;
    /**
     * 子节点
     */
    private List<TreeNode> childList;

    public TreeNode() {
    }

    public TreeNode(Integer id, String name, Integer parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

工具类：搭配注释很容易看懂

import com.example.tree.entity.TreeNode;
import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * @description:
 * @author: LoneWalker
 * @create: 2022-11-28
 **/
public class TreeUtil {

    /**
     * 获取所有的根节点
     */
    public static <T extends TreeNode> List<T> getRootNode(List<T> treeNodeList,Set<Integer> nodeIdSet){
        List<T> rootNodeList = new ArrayList<>();
        for (T treeNode : treeNodeList) {
            if (0 == treeNode.getParentId() || null == treeNode.getParentId()){
                rootNodeList.add(treeNode);
                nodeIdSet.add(treeNode.getId());
            }
        }
        return rootNodeList;
    }

    /**
     * 构建树
     */
    public static <T extends TreeNode> T buildChildTree(T rootNode,List<T> treeNodeList,Set<Integer> nodeIdSet){
        List<T> childNodeList = new ArrayList<>();
        for (T treeNode : treeNodeList) {
            if (!nodeIdSet.contains(treeNode.getId()) && treeNode.getParentId().equals(rootNode.getId())){
                    nodeIdSet.add(treeNode.getId());
                    //这里相当于把当前节点又作为父节点 递归查询子节点
                    childNodeList.add(buildChildTree(treeNode,treeNodeList,nodeIdSet));
            }
        }
        rootNode.setChildList((List<TreeNode>) childNodeList);
        return rootNode;
    }

    public static <T extends TreeNode> List<T> buildTree(List<T> treeNodeList){

        if (CollectionUtils.isEmpty(treeNodeList)){
            return Collections.emptyList();
        }
        //用来保存每一棵完整的树
        List<T> treeNodes = new ArrayList<T>();
        //用来保存已装填过的树节点ID 防止重复遍历
        Set<Integer> nodeIdSet = new HashSet<>();
        for (T root : getRootNode(treeNodeList,nodeIdSet)) {
            T treeNode = buildChildTree(root, treeNodeList,nodeIdSet);
            treeNodes.add(treeNode);
        }
        return treeNodes;
    }
}

测试

@RestController
public class TreeController {

    @GetMapping("/listTree")
    public List<TreeNode> listTree(){
        //模拟数据
        List<TreeNode> treeNodeList = new ArrayList<>();
        treeNodeList.add(new TreeNode(1,"顶级节点A",0));
        treeNodeList.add(new TreeNode(2,"顶级节点B",0));
        treeNodeList.add(new TreeNode(3,"二级节点A1",1));
        treeNodeList.add(new TreeNode(4,"二级结点B1",2));
        treeNodeList.add(new TreeNode(5,"二级节点B2",2));
        treeNodeList.add(new TreeNode(6,"三级节点A1-1",3));
        treeNodeList.add(new TreeNode(7,"三级节点A1-2",3));
        treeNodeList.add(new TreeNode(8,"四级节点A1-1-1",6));
        treeNodeList.add(new TreeNode(9,"四级节点A1-1-2",6));
        treeNodeList.add(new TreeNode(10,"五级节点A1-1-1-1",8));
        long start = System.currentTimeMillis();
        List<TreeNode> treeNodes = TreeUtil.buildTree(treeNodeList);
        System.out.println("耗时："+(System.currentTimeMillis() - start));
        return treeNodes;
    }
}

3、非递归构建树

    public static <T extends TreeNode> List<T> buildTree(List<T> treeNodeList){
        List<T> rootNodeList = new ArrayList<>();
        //移除根数据
        rootNodeList = treeNodeList.stream().filter(d -> d.getParentId() == null || d.getParentId() == 0).collect(Collectors.toList());
        treeNodeList.removeAll(rootNodeList);
        //根据父节点分组
        Map<Integer, List<T>> childMap = treeNodeList.stream().collect(Collectors.groupingBy(T::getParentId));
        //设置子节点[这里不包括根节点]
        treeNodeList.forEach(treeNode -> treeNode.setChildList(castList(childMap.get(treeNode.getId()),TreeNode.class)));
        //将上面已经构建的子树拼到对应的根节点上
        return rootNodeList.stream().peek(root -> root.setChildList(castList(childMap.get(root.getId()),TreeNode.class))).collect(Collectors.toList());
    }

    /**
     * 这部分不是必要的，childMap.get(treeNode.getId())强转也行
     */
    public static <T> List<T> castList(Object obj, Class<T> clazz)
    {
        List<T> result = new ArrayList<T>();
        if(obj instanceof List<?>) {
            for (Object o : (List<?>) obj)
            {
                result.add(clazz.cast(o));
            }
            return result;
        }
        return null;
    }

4、扩展

4.1递归为什么效率低

递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N局部变量、N形参、N调用函数地址、N返回值，这势必是影响效率的，同时，这也是内存溢出的原因，因为积累了大量的中间变量无法释放。

4.2 Stream效率问题

在少低数据量的处理场景中（size<=1000），stream 的处理效率是不如传统的 iterator 外部迭代器处理速度快的，但是实际上这些处理任务本身运行时间都低于毫秒，这点效率的差距对普通业务几乎没有影响，反而 stream 可以使得代码更加简洁。

4.3 removeIf和迭代器 remove效率对比

测试1000000份数据，删除一半数据
removeIf() 22ms
iterator.remove 39962ms