本文介绍一种高效、非递归但逻辑等价于递归的算法，将扁平的节点数组按 parent-id 关系构建成嵌套的树形结构，适用于文件系统、菜单、组织架构等场景。
本文介绍一种高效、非递归但逻辑等价于递归的算法，将扁平的节点数组按 parent-id 关系构建成嵌套的树形结构，适用于文件系统、菜单、组织架构等场景。
在前端开发中，常需将 API 返回的扁平化节点列表（如文件/文件夹列表）转换为具有父子关系的树形结构。虽然问题描述中提到了“递归函数”，但实际最优解往往**不依赖显式递归调用**——而是采用一次遍历 + 哈希映射（Map）的策略，时间复杂度 O(n)，空间复杂度 O(n)，且天然支持任意深度嵌套，避免栈溢出风险。
核心思路如下：
- 使用 Map 缓存所有已处理节点（以 id 为键），确保任意节点可被快速查找和复用；
- 维护一个 roots 数组，收集所有无 parent 字段的顶层节点；
- 遍历每个节点时：
- 若为 'FOLDER' 类型，统一初始化 children: []（即使暂无子节点）；
- 若存在 parent，则确保其父节点（即使尚未出现）已在 Map 中存在，并将当前节点推入其 children 数组；
- 若无 parent，直接加入 roots。
以下是完整、可运行的实现代码（含修复与优化）：
function buildTree(data) {
const nodes = new Map();
const roots = [];
data.reduce((acc, item) => {
// 确保 folder 节点始终有 children 数组
const node = item.type === 'FOLDER'
? { ...item, children: acc.nodes.get(item.id)?.children || [] }
: { ...item };
// 存入 Map（覆盖或新增）
acc.nodes.set(item.id, node);
if (!item.parent) {
// 顶层节点：无 parent，直接入 roots
acc.roots.push(node);
} else {
// 确保 parent 节点存在（即使数据中尚未出现该 parent）
if (!acc.nodes.has(item.parent)) {
acc.nodes.set(item.parent, { id: item.parent, children: [] });
}
// 将当前节点添加到 parent 的 children 中
acc.nodes.get(item.parent).children.push(node);
}
return acc;
}, { nodes, roots });
return roots;
}
// 示例数据
const data = [
{ id: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b949', conditions: 'string', type: 'FOLDER' },
{ id: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b948', conditions: 'string', type: 'FOLDER', parent: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b949' },
{ id: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b957', conditions: 'string', type: 'STANDARD', parent: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b948' },
{ id: 'node_292f637b-b33d-4d3d-bc96-8afc7ee1b936', conditions: 'string', type: 'STANDARD' }
];
console.log(buildTree(data));
✅ 关键注意事项：
- 无需预先排序：算法对输入顺序不敏感，即使子节点出现在父节点之前也能正确关联（得益于 Map 的延迟创建机制）；
- 类型语义清晰：FOLDER 节点强制初始化 children: []，便于后续动态增删；STANDARD 节点保持原样，不强制添加空 children；
- 健壮性保障：自动创建缺失的父节点占位符（如 parent ID 在原始数据中未定义），避免运行时错误；
- 性能优势：单次 reduce 遍历完成全部构建，比多层 filter + 显式递归更高效，也规避了重复遍历开销。
该方案本质是“自底向上”的隐式递归建树，既满足业务对无限嵌套层级的需求，又兼顾性能、可读性与工程鲁棒性，是构建前端树形结构的推荐实践。
