递归构建树形目录结构方法

本文揭秘了一种高效构建树形结构的“伪递归”算法——它虽逻辑上等价于递归，却完全规避了显式递归调用，通过一次遍历配合哈希映射（Map）实现 O(n) 时间复杂度的扁平数据到嵌套树的转换，不仅支持任意深度、无需预排序、自动补全缺失父节点，还彻底消除栈溢出风险，特别适合文件系统、动态菜单和组织架构等真实前端场景，是兼顾性能、健壮性与可维护性的工程级最佳实践。

本文介绍一种高效、非递归但逻辑等价于递归的算法，将扁平的节点数组按 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 + 显式递归更高效，也规避了重复遍历开销。

该方案本质是“自底向上”的隐式递归建树，既满足业务对无限嵌套层级的需求，又兼顾性能、可读性与工程鲁棒性，是构建前端树形结构的推荐实践。

本篇关于《递归构建树形目录结构方法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！