树结构

1. 栈, 如果善于利用栈来处理树结构, 那么可以写出更简洁的代码, 根本不需要 recuresiveFn 这种方法.
2. 泛型, 如果善于利用泛型, 那么可以写出更通用的代码，而不是耦合于某一种类型。算法复杂度, 这段代码的时间复杂度是 N*N , 典型的暴力算法
3. 代码结构, 写这段代码的人, 虽然有“拆分冗长逻辑为一个方法“ 的意识, 但是, 就其解决的问题而言, 代码可以更简洁.
4. 命名,TreeUtil 是一个很“泛”的命名, 可是其内容中的 MenuTreeObject 却很“具体 ”, 两个 “域” 不匹配. (封面与内容不匹配)

第一版是时间复杂度 O(N^2) 的版本

interface ITreeNode<T extends ITreeNode<T>> {
    T parent();

    void setChildren(List<T> children);

    List<T> getChildren();
}

class TreeUtil {
    public static <T extends ITreeNode<T>> List<T> listToTree(List<T> list) {
    
        var roots = list.stream()
                .filter(n -> n.parent() == null)
                .collect(Collectors.toList());
    
        var stack = roots.stream().collect(Collectors.toCollection(Stack::new));
    
        while (!stack.isEmpty()) {
            var node = stack.pop();
            //每一个元素都需要跟其他所有元素比较,时间复杂度 N*N
            node.setChildren(
                    list.stream()
                            .filter(n -> n.parent() != null)
                            .filter(n -> n.parent().equals(node))
                            .collect(Collectors.toList()));
    
            node.getChildren().forEach(stack::push);
        }
        return roots;
    }
}

第二版利用动态规划的思想, 分解出“自顶向下构建树”的子问题：“给定一个节点，其子节点有哪些”。只需一次遍历，缓存每一个节点的 父子关系 ，即可得到每个节点，对于这个子问题的结果。之后便可以自顶向下地构建树。 在构建过程中，每处理一个节点，都是直接从缓存取其子节点，没有重复计算（不需要重复访问不相关的节点），复杂度从平方级降为线性。

class TreeUtil {
    public static <T extends ITreeNode<T>> List<T> listToTree2(List<T> list) {
        //第一次遍历: 记录节点间的父子关系
        var relations = new HashMap<T, List<T>>();
        for (T node : list) {
            List<T> relation = relations.computeIfAbsent(node.parent(), (p) -> new LinkedList<>());
            relation.add(node);
        }
        var roots = relations.get(null); //父节点为null的即为根节点
        //第二次遍历: 根据父子关系建立树
        var stack = roots.stream().collect(Collectors.toCollection(Stack::new));
        while (!stack.isEmpty()) {
            T node = stack.pop();
            node.setChildren(relations.getOrDefault(node, Collections.emptyList()));
            stack.addAll(node.getChildren());
        }
        return roots;
    }
}

测试代码

static class MenuItem implements ITreeNode<MenuItem> {

    private Integer id;
    private String name;
    private Integer parentId;

    public MenuItem(Integer id) {
        this.id = id;
    }

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

    @Getter
    @Setter
    private List<MenuItem> children;

    @Override
    public MenuItem parent() {
        return parentId == null ? null : new MenuItem(parentId);
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof MenuItem && Objects.equals(id, ((MenuItem) o).id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public static void main(String[] args) {
        List<MenuItem> menuList = Arrays.asList(
                new MenuItem(1, "一级菜单", null),
                new MenuItem(2, "二级菜单1", 1),
                new MenuItem(3, "二级菜单2", 1),
                new MenuItem(3, "三级菜单1", 2),
                new MenuItem(4, "三级菜单2", 2)
        );

        List<MenuItem> menuTree = TreeUtil.listToTree2(menuList);
        System.out.println(menuTree);
    }

引入一个hashmap，时间复杂度由 O(N*N*N) 变为 O(NlogN)，一个for循环就搞定了。
public List<MenuTreeObject> getTree(List<MenuTreeObject> list) {
    Map<Integer, MenuTreeObject> menuMap = list.stream().collect(Collectors.toMap(MenuTreeObject::getId, Function.identity()));
    List<MenuTreeObject> rootList = new ArrayList<>(); //根节点列表
    list.forEach(menuTreeObject -> {
        var parent = menuMap.get(menuTreeObject.getParentId());
        if(parent != null) {
           parent.getChildren().add(menuTreeObject);  
        } else { //没有父节点的菜单为根节点
           rootList.add(menuTreeObject);
        }
    });
    return rootList;
}