java - 从平面列表生成嵌套列表(树)

我在java中有一个名为menumodel的普通类（顾名思义是用于嵌套菜单），如下所示：

public class MenuModel {
    public String id;
    public String parentId = null;
    public String title;

    public MenuModel parent = null;
    public List<MenuModel> children = new ArrayList<MenuModel>();
 }

我的代码从web API获取数据，并生成一个MenuModel的平面列表，其中只有id、parentId和title字段填充了数据但是，我需要每个menumodel都有对其父级和（可选）子级的引用，以便进一步使用。
我想到了一种方法，它生成一个嵌套循环，以使模型彼此配对，并检查它们是否是父模型和子模型。但是我认为成本太高（n ^ 2或n^ 3复杂度，项目集很大），只能填充parent字段。
在Java中实现这一点的最佳方法是什么总结一下：
输入：ArrayList<MenuModel> source
输出：ArrayList<MenuModel> result包含源中所有具有parentId = null的menumodel（也就是说，它是顶级菜单），每个menumodel都有子字段，这些子字段都是引用各自的子menumodel填充的。此外，每个孩子都会提到他们的父母。
提前谢谢

最佳答案

浏览所有记录并将它们添加到HashMap<String, MenuModel>（关键是id）。
然后，对于每个记录：
在上面的映射中查找父ID以获得record。
将父项分配给此记录的父变量-parent。
将此记录添加到父级的子级列表-record.parent = parent。
运行时间：预期O（N）。