Hutool TreeUtil 列表转树与两遍扫描法

这篇笔记记录列表转树的实现方式。部门、菜单、商品分类这类数据在数据库中以平铺的行记录存储，前端组件和递归算法通常需要嵌套结构，转换工作落在后端。Hutool 的 TreeUtil.buildSingle 是完成这项转换的常用工具，下文先用 JDK 手写一遍，再对照 Hutool 的写法。

示例数据为四条部门记录，字段包括 id、parentId 和 name。

转换结果为 A 包含 B 和 C 两个子节点，B 包含 D 一个子节点。

扁平列表的含义

这里的扁平，针对的是存储结构一层。数据在逻辑上仍然是一棵树，父子关系完整存在，只是没有以嵌套形式存放。

List 里四个元素平铺排列，是一维的，彼此独立。

[Dept(A), Dept(B), Dept(C), Dept(D)]

它们之间没有嵌套，没有引用链，List 本身不记录每个元素的父节点。父子关系藏在每个元素的 parentId 字段里，是一种隐式引用，需要靠 id 查表才能还原。

这种存储形式在数据结构里叫邻接表表示法，英文 adjacency list。数据库里存树、Excel 里存层级，基本都是这种形式，一行对应一个节点，每行记录父节点的 id。它的优点是维护成本低，新增、删除、移动节点都只需要修改一行，移动一个部门只需要改动该部门记录的 parentId。

转换做的事情，是把父子关系从隐式引用改成显式嵌套。输入中关系靠 parentId 外键表达，查找子节点需要遍历列表逐条匹配。输出中关系靠 children 列表表达，父节点直接持有子节点的引用，沿引用向下遍历即可。转换前后数据的条数和字段内容保持不变，变化的只有关系的表达方式。

这一转换成立的前提，是输入数据带有完整的 parentId 信息。没有 parentId 的平铺数据不包含层级信息，无法直接构成树，只能另行制定分层规则，例如按编码前缀分组。

两遍扫描法

手写实现通常采用两遍扫描，整体是两个循环。

第一遍建立索引。遍历列表，为每个业务对象创建对应的树节点，并以 id 为键存入 HashMap。

第二遍建立父子关系。再次遍历列表，用每个节点的 parentId 从 HashMap 中取出父节点，把当前节点加入父节点的 children。parentId 等于约定根值，例如 0 或 null 的节点，即为根节点。

两遍扫描的时间复杂度为 O(n)，每个节点被处理的次数是常数级。另一种常见写法是递归查找，每确定一层子节点就扫描一次全表，时间复杂度为 O(n²)。数据规模在几千到几万行时，两种写法的耗时差距会变得明显。两遍扫描额外占用的是一份 HashMap 索引，空间复杂度 O(n)。

两遍扫描对输入顺序没有要求。子节点排在父节点之前不影响结果，第一遍结束时全部节点已经进入 HashMap，第二遍连线时父节点必然可以查到。递归写法对顺序更敏感，输入未按层级排序时容易漏掉节点。

排序在连线完成之后处理。节点带有 weight 或 sort 字段时，对每个节点的 children 分别排序即可。在连线之前对全表排序同样可行，插入顺序会保留到 children 中。

JDK 实现

两遍扫描用 JDK 实现的代码如下，Dept 是包含 id、parentId、name 和 children 四个字段的普通类。

public static Dept buildSingle(List<Dept> list, long rootParentId) {
    Map<Long, Dept> map = new HashMap<>();
    for (Dept dept : list) {
        map.put(dept.getId(), dept);
    }
    Dept root = null;
    for (Dept dept : list) {
        if (dept.getParentId() == rootParentId) {
            root = dept;
            continue;
        }
        Dept parent = map.get(dept.getParentId());
        if (parent != null) {
            parent.getChildren().add(dept);
        }
    }
    return root;
}

多根节点的场景对应森林结构。把返回值由单个 root 改为列表，第二遍中 parentId 等于根值的节点逐个加入列表，其余代码保持不变。

Hutool TreeUtil 的用法

Hutool 是国产开源的 Java 工具类库，定位是小而全的工具集合，用静态工具方法替代日常的样板代码。TreeUtil 是其中的树结构工具类，buildSingle 用于单根树，build 用于多根森林并返回 List。

buildSingle 的参数有三部分，扁平数据列表、根节点的 parentId 值、业务对象到树节点的转换逻辑。业务字段与树节点字段的对应关系在转换逻辑中声明。

Tree<Long> tree = TreeUtil.buildSingle(list, 0L, (dept, node) -> {
    node.setId(dept.getId());
    node.setParentId(dept.getParentId());
    node.setName(dept.getName());
    node.setWeight(dept.getSort());
});

Tree 是 Hutool 提供的节点类型，内置 id、parentId、name、weight 和 children 字段，并支持通过 putExtra 写入扩展字段，序列化为 JSON 后即为嵌套结构。节点字段名与默认值不一致时，可以通过 TreeNodeConfig 修改 id、parentId、children 等字段的键名，也可以设置最大深度。输入数据本身已经是 TreeNode 列表时，调用 TreeUtil.build(nodeList, "0") 即可完成转换。

从实现上看，buildSingle 内部执行的仍然是两遍扫描。工具封装的意义在于把排序、深度限制、扩展字段和多根处理做成统一的实现，避免同一项目中出现多份逻辑略有差异的树构建代码。

边界情况

根节点的约定需要与数据保持一致。数据库中根节点的 parentId 存为 null，代码按 0 查找根节点时，结果为空树。反之，数据中存在 id 为 0 的真实节点时，按 0 约定的判断会与之冲突。根值的取值应当在读取数据前与表结构核对。

孤儿节点指 parentId 指向不存在 id 的记录。第二遍连线时，这类节点查不到父节点，在上面的手写实现中会被直接跳过，对应到业务上就是菜单缺项或部门缺失。处理方式由业务决定，常见做法是构建时报错，或者把孤儿节点作为根节点保留，使问题可以在结果中直接看到。

环形引用指节点之间互为祖先，例如 A 的 parentId 是 B，B 的 parentId 又是 A。这类数据连线后找不到根节点，序列化时还可能沿 children 形成无限递归。TreeUtil 默认不检测环，数据来源复杂时，可以在构建前逐个节点沿 parentId 向上追溯到根，无法到达根节点的记录单独处理。

重复 id 会在第一遍被 HashMap 的 put 覆盖，后写入的节点替换先写入的节点，被替换节点及其子节点随之丢失。id 来自主键时一般不会出现重复，数据来自多表拼接或外部文件导入时，需要在构建前做一次唯一性检查。

Hutool 与 JDK 的功能对照

Hutool 的一部分方法补的是 JDK 的空缺，空缺的位置随 JDK 版本变化，需要分开看。StrUtil.isBlank 对应的字符串判空，JDK 11 已在 String 中提供 isBlank 方法。UUID 随机生成是 JDK 自带能力，Hutool 的封装属于重复提供。BeanUtil.copyProperties 是反射属性拷贝，Spring 的 BeanUtils 提供相同功能。CollUtil.isEmpty 等集合判空和 CollUtil.split 等分批处理，JDK 目前没有直接对应的方法。

JSON 解析和 CSV 读写，JDK 至今没有提供原生实现。HttpRequest 封装的是 HttpURLConnection 的用法，JDK 11 引入的 HttpClient 是功能相近的官方方案。综合来看，Hutool 的价值主要在方法风格统一和调用简短，减少每个项目重复编写工具类的工作量。

具体到列表转树，选型可以按两种情况处理。项目已经引入 Hutool 时，直接使用 TreeUtil，边界处理有现成的配置项。项目未引入 Hutool 且只有个别脚本需要转换时，手写两遍扫描即可，为单个方法引入完整依赖并不划算。多个模块都会用到树构建时，把两遍扫描收进项目自身的工具类，是介于两者之间的做法。

小结

列表转树更准确的描述，是把以 parentId 外键表示的树转换为以 children 嵌套引用表示的树，也就是把隐式引用换成显式嵌套。存储形式发生变化，数据携带的父子关系不变。两遍扫描是这一转换的基本实现，时间复杂度 O(n)，Hutool TreeUtil 在此基础上提供字段映射、排序、深度限制和扩展字段等封装。