一维数组转换为树状数组

    题目描述

    将下列数据按照父子关系转换为树状的数组

    const flatData = [
  { id: 1, name: '部门A', parentId: 0 }, // parentId 为 0 通常代表根节点
  { id: 2, name: '部门B', parentId: 1 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 2 },
  { id: 5, name: '部门E', parentId: 0 },
];

    解题思路

    哈希表

    1. 建表：遍历一次扁平数组，将每个节点以 id 为键存入 Map，同时为每个节点初始化空的 children 数组。此时所有节点都在表中，互相独立。
    2. 建关系：再次遍历 Map，对每个节点取出其 parentId，直接到 Map 中进行 O(1) 查找：
      • 找到父节点 → 将自身 push 进父节点的 children
      • 找不到父节点（parentId 无效或为 0）→ 视为根节点，收入结果数组

    递归

    对当前层的每个节点，把它自身的 id 作为新的 parentId，再次调用自身，得到它的下一层子节点，挂到 children 上。

    复杂度分析

    哈希表解法

    • 时间复杂度：O(n)
      遍历两次数组（建表 + 建关系），每次操作均为 O(1)，整体为 O(n)。

    • 空间复杂度：O(n)
      Map 中存储 n 个节点，额外空间为 O(n)。

    递归解法

    • 时间复杂度：O(n²)
      每次递归调用都对整个数组执行一次 filter（O(n)），而递归总共会被调用 n + 1 次（根调用 1 次 + 每个节点各调用 1 次），因此总时间复杂度为 O(n²)。

    • 空间复杂度：O(n)
      输出结果包含所有 n 个节点（O(n)），递归调用栈深度等于树的深度 d（O(d)）。最坏情况下（退化为链表）d = n，空间复杂度为 O(n)。

    示例代码

    哈希表解法
    递归解法
    export function arrayToTree(arr) {
  // 入参校验：非数组或空数组直接返回空结果
  if (!Array.isArray(arr) || arr.length === 0) {
    return [];
  }

  // 构建哈希表：以 id 为键，方便 O(1) 查找父节点
  const arrMap = new Map();

  // 将每个节点存入 Map，同时初始化 children 数组
  for (const item of arr) {
    arrMap.set(item.id, { ...item, children: [] });
  }

  const result = [];
  arrMap.forEach((it) => {
    // 根据当前节点的 parentId 查找父节点
    const parent = arrMap.get(it.parentId);
    if (parent) {
      // 父节点存在，将当前节点挂载到父节点的 children 下
      parent.children.push(it);
    } else {
      // 父节点不存在（parentId 为 0 或无效），视为根节点
      result.push(it);
    }
  });

  // 返回仅包含根节点的树状数组
  return result;
}

// 测试
const flatData = [
  { id: 1, name: '部门A', parentId: 0 }, // parentId 为 0 通常代表根节点
  { id: 2, name: '部门B', parentId: 1 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 2 },
  { id: 5, name: '部门E', parentId: 0 },
];
console.log(JSON.stringify(arrayToTree(flatData)));