这种数据和嵌套对象相互转换的题目，在手写题环节很常见，今天我们就来介绍几种解法。

方法一

很容易想到的一个方法就是利用递归：每次遍历时，找到将本次遍历的根节点作为父节点的所有子节点，直至找不到有子节点的。

复制
1/**
2 * 数组转树形结构
3 * @param {array} list 被转换的数组
4 * @param {number|string} root 根节点（最外层节点）
5 * @returns array
6 */
7function arrayToTree(list, root) {
8  return list
9    .filter(item => item.parent_id === root)
10    .map(item => ({ ...item, children: arrayToTree(list, item.id) }))
11}

代码很简洁，filter 和 map 方法也是数组中很常见的方法，相信大家也很好理解。

方法二

可以利用浅拷贝是拷贝对象的内存地址的特性，我们修改拷贝后，所有引用都会同步修改。利用这个特点，我们将子节点依次放入父节点，最后将最外层父节点返回即可。

复制
1/**
2 * 数组转树形结构
3 * @param {array} list 被转换的数组
4 * @param {number|string} root 根节点（最外层节点）的 id
5 * @return array
6 */
7function arrayToTree(list, root) {
8  const result = [] // 用于存放结果
9  const map = {} // 用于存放 list 下的节点
10
11  // 1. 遍历 list，将 list 下的所有节点以 id 作为索引存入 map
12  for (const item of list) {
13    map[item.id] = { ...item } // 浅拷贝
14  }
15
16  // 2. 再次遍历，将根节点放入最外层，子节点放入父节点
17  for (const item of list) {
18    // 3. 获取节点的 id 和 父 id
19    const { id, parent_id } = item // ES6 解构赋值
20    // 4. 如果是根节点，存入 result
21    if (item.parent_id === root) {
22      result.push(map[id])
23    } else {
24      // 5. 反之，存入到父节点
25      map[parent_id].children
26        ? map[parent_id].children.push(map[id])
27        : (map[parent_id].children = [map[id]])
28    }
29  }
30
31  // 将结果返回
32  return result
33}

代码中有注释，相信大家多读几遍也能理解。

方法三

针对方法二，我们也可以有些优化，只需要一次遍历，就能获取到结果

复制
1/**
2 * 数组转树形结构
3 * @param {array} list 被转换的数组
4 * @param {number|string} root 根节点（最外层节点）
5 * @returns array
6 */
7function arrayToTree(list, root) {
8  const result = [] // 用于存放结果
9  const map = {} // 用于存放 list 下的节点
10
11  // 遍历 list
12  for (const item of list) {
13    // 1. 获取节点的 id 和 父 id
14    const { id, parent_id } = item // ES6 解构赋值
15
16    // 2. 将节点存入 map
17    if (!map[id]) map[id] = {}
18
19    // 3. 根据 id，将节点与之前存入的子节点合并
20    map[id] = map[id].children
21      ? { ...item, children: map[id].children }
22      : { ...item }
23
24    // 4. 如果是根节点，存入 result
25    if (parent_id === root) {
26      result.push(map[id])
27    } else {
28      // 5. 反之，存入父节点
29      if (!map[parent_id]) map[parent_id] = {}
30      if (!map[parent_id].children) map[parent_id].children = []
31      map[parent_id].children.push(map[id])
32    }
33  }
34
35  // 将结果返回
36  return result
37}