算法题：将扁平化数组转换为树形结构

1. 问题描述

给定一个包含节点对象的扁平化数组，其中每个对象都含有 id, value, parent (父节点ID) 等属性。任务是根据 id 和 parent 的关联关系，将这个扁平化数组高效地转换成一个或多个树形结构。

这是一个常见的面试题，重点考察对时间复杂度的理解和优化能力。

2. 核心挑战

主要挑战在于 如何高效地为每个节点找到其对应的父节点。

直接查找：遍历数组为每个节点寻找父节点，会导致时间复杂度过高。
优化查找：需要找到一种方法，将查找父节点的时间复杂度从 $O(n)$ 降至 $O(1)$。

3. 解法分析

解法一：暴力法（不推荐）

思路:
1. 遍历原始数组中的每一个节点。
2. 对于当前节点，再次遍历整个数组，查找 id 与当前节点的 parent 值相匹配的节点，即为其父节点。
3. 将当前节点添加到父节点的 children 数组中。
时间复杂度: $O(n^2)$
- 外层循环遍历所有节点，复杂度为 $O(n)$。
- 内层循环为每个节点查找父节点，复杂度也为 $O(n)$。
- 总复杂度为 $O(n) \times O(n) = O(n^2)$。

解法二：空间换时间优化（推荐）

通过使用额外的数据结构（如 Map 或哈希表），可以显著降低查找父节点的时间成本。

思路:
1. 建立映射：先用一次遍历，将数组中所有节点的 id 和节点对象本身存入一个 Map 中，形成 id -> node 的映射关系。这一步的时间复杂度为 $O(n)$。
2. 构建树结构：再次遍历原始数组。对于每个节点：
  - 通过其 parent 属性值，直接从 Map 中以 $O(1)$ 的时间复杂度获取父节点。
  - 判断根节点：如果一个节点的 parent 为 null 或不存在，则它是一个根节点，将其存入最终结果数组 roots。
  - 关联子节点：如果节点存在父节点，则将该节点添加到其父节点的 children 数组中。（注意：首次添加时可能需要初始化父节点的 children 数组）。
时间复杂度: $O(n)$
- 第一次遍历创建 Map：$O(n)$。
- 第二次遍历构建树：$O(n)$。其中查找父节点为 $O(1)$。
- 总复杂度为 $O(n) + O(n) = O(n)$。
空间复杂度: $O(n)$
- 需要一个额外的 Map 来存储所有节点的映射，占用了 $O(n)$ 的空间。

4. 代码实现 (JavaScript)

javascript

/**
 * 将扁平化数组转换为树形结构（森林）
 * @param {Array<Object>} list 包含节点对象的数组
 * @returns {Array<Object>} 根节点组成的数组（森林）
 */
function arrayToTree(list) {
  // 1. 定义最终结果数组，用于存放所有根节点
  const roots = [];
  
  // 2. 定义一个 Map，用于空间换时间，实现 O(1) 复杂度的节点查找
  // key: 节点 id, value: 节点对象本身
  const map = new Map();

  // 3. 第一次遍历：填充 Map，建立 id -> node 的映射关系
  list.forEach(node => {
    map.set(node.id, node);
  });

  // 4. 第二次遍历：构建树结构
  list.forEach(node => {
    // 检查当前节点是否有父节点
    if (node.parent !== null) {
      // 从 Map 中 O(1) 复杂度找到父节点
      const parentNode = map.get(node.parent);
      
      // 如果父节点存在
      if (parentNode) {
        // 如果父节点的 children 属性还未初始化，则初始化为空数组
        if (!parentNode.children) {
          parentNode.children = [];
        }
        // 将当前节点添加到父节点的 children 数组中
        parentNode.children.push(node);
      }
    } else {
      // 如果 parent 为 null，说明是根节点，直接加入到 roots 数组
      roots.push(node);
    }
  });

  return roots;
}

// --- 示例 ---
const inputArray = [
  { id: 1, value: '节点1', parent: null },
  { id: 2, value: '节点2', parent: 1 },
  { id: 3, value: '节点3', parent: 1 },
  { id: 4, value: '节点4', parent: 2 },
  { id: 5, value: '节点5', parent: 2 },
  { id: 6, value: '节点6', parent: null },
  { id: 7, value: '节点7', parent: 6 }
];

const tree = arrayToTree(inputArray);

// 使用 console.log 打印完整结构
console.log(JSON.stringify(tree, null, 2));

/*
输出结果:
[
  {
    "id": 1,
    "value": "节点1",
    "parent": null,
    "children": [
      {
        "id": 2,
        "value": "节点2",
        "parent": 1,
        "children": [
          { "id": 4, "value": "节点4", "parent": 2 },
          { "id": 5, "value": "节点5", "parent": 2 }
        ]
      },
      { "id": 3, "value": "节点3", "parent": 1 }
    ]
  },
  {
    "id": 6,
    "value": "节点6",
    "parent": null,
    "children": [
      { "id": 7, "value": "节点7", "parent": 6 }
    ]
  }
]
*/

5. 关键点与注意事项

考虑多根节点（森林）：输入数据可能不是单棵树，而是一个森林。因此，最终结果应该是一个数组，包含所有根节点。
ID 的唯一性：该算法成立的前提是节点的 id 是唯一的。
初始化 children 数组：在向父节点添加子节点时，必须检查 children 属性是否存在，如果不存在需要先初始化为一个空数组。
空间换时间：这是算法优化的核心思想。使用 Map 将查找操作的复杂度从 $O(n)$ 降为 $O(1)$，是性能提升的关键。

算法题：将扁平化数组转换为树形结构 ​

1. 问题描述 ​

2. 核心挑战 ​

3. 解法分析 ​

解法一：暴力法（不推荐） ​

解法二：空间换时间优化（推荐） ​

4. 代码实现 (JavaScript) ​

5. 关键点与注意事项 ​