将下面的数组转成树状结构

根据 id 和 parent_id 的对应关系，进行下面的转换。

原始数据：

[
  { "id": 12, "parent_id": 1, "name": "朝阳区" },
  { "id": 241, "parent_id": 24, "name": "田林街道" },
  { "id": 31, "parent_id": 3, "name": "广州市" },
  { "id": 13, "parent_id": 1, "name": "昌平区" },
  { "id": 2421, "parent_id": 242, "name": "上海科技绿洲" },
  { "id": 21, "parent_id": 2, "name": "静安区" },
  { "id": 242, "parent_id": 24, "name": "漕河泾街道" },
  { "id": 22, "parent_id": 2, "name": "黄浦区" },
  { "id": 11, "parent_id": 1, "name": "顺义区" },
  { "id": 2, "parent_id": 0, "name": "上海市" },
  { "id": 24, "parent_id": 2, "name": "徐汇区" },
  { "id": 1, "parent_id": 0, "name": "北京市" },
  { "id": 2422, "parent_id": 242, "name": "漕河泾开发区" },
  { "id": 32, "parent_id": 3, "name": "深圳市" },
  { "id": 33, "parent_id": 3, "name": "东莞市" },
  { "id": 3, "parent_id": 0, "name": "广东省" }
]

转换后的结构：

[
  {
    "id": 2,
    "parent_id": 0,
    "name": "上海市",
    "children": [
      {
        "id": 21,
        "parent_id": 2,
        "name": "静安区",
        "children": []
      },
      {
        "id": 22,
        "parent_id": 2,
        "name": "黄浦区",
        "children": []
      },
      {
        "id": 24,
        "parent_id": 2,
        "name": "徐汇区",
        "children": [
          {
            "id": 241,
            "parent_id": 24,
            "name": "田林街道",
            "children": []
          },
          {
            "id": 242,
            "parent_id": 24,
            "name": "漕河泾街道",
            "children": [
              {
                "id": 2421,
                "parent_id": 242,
                "name": "上海科技绿洲",
                "children": []
              },
              {
                "id": 2422,
                "parent_id": 242,
                "name": "漕河泾开发区",
                "children": []
              }
            ]
          }
        ]
      }
    ]
  },
  {
    "id": 1,
    "parent_id": 0,
    "name": "北京市",
    "children": [
      {
        "id": 12,
        "parent_id": 1,
        "name": "朝阳区",
        "children": []
      },
      {
        "id": 13,
        "parent_id": 1,
        "name": "昌平区",
        "children": []
      },
      {
        "id": 11,
        "parent_id": 1,
        "name": "顺义区",
        "children": []
      }
    ]
  },
  {
    "id": 3,
    "parent_id": 0,
    "name": "广东省",
    "children": [
      {
        "id": 31,
        "parent_id": 3,
        "name": "广州市",
        "children": []
      },
      {
        "id": 32,
        "parent_id": 3,
        "name": "深圳市",
        "children": []
      },
      {
        "id": 33,
        "parent_id": 3,
        "name": "东莞市",
        "children": []
      }
    ]
  }
]

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

方法一

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

/**
 * 数组转树形结构
 * @param {array} list 被转换的数组
 * @param {number|string} root 根节点（最外层节点）
 * @returns array
 */
function arrayToTree(list, root) {
  return list
    .filter((item) => item.parent_id === root)
    .map((item) => ({ ...item, children: arrayToTree(list, item.id) }));
}

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

方法二

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

/**
 * 数组转树形结构
 * @param {array} list 被转换的数组
 * @param {number|string} root 根节点（最外层节点）的 id
 * @return array
 */
function arrayToTree(list, root) {
  const result = []; // 用于存放结果
  const map = {}; // 用于存放 list 下的节点

  // 1. 遍历 list，将 list 下的所有节点以 id 作为索引存入 map
  for (const item of list) {
    map[item.id] = { ...item }; // 浅拷贝
  }

  // 2. 再次遍历，将根节点放入最外层，子节点放入父节点
  for (const item of list) {
    // 3. 获取节点的 id 和 父 id
    const { id, parent_id } = item; // ES6 解构赋值
    // 4. 如果是根节点，存入 result
    if (item.parent_id === root) {
      result.push(map[id]);
    } else {
      // 5. 反之，存入到父节点
      map[parent_id].children
        ? map[parent_id].children.push(map[id])
        : (map[parent_id].children = [map[id]]);
    }
  }

  // 将结果返回
  return result;
}

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

方法三

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

/**
 * 数组转树形结构
 * @param {array} list 被转换的数组
 * @param {number|string} root 根节点（最外层节点）
 * @returns array
 */
function arrayToTree(list, root) {
  const result = []; // 用于存放结果
  const map = {}; // 用于存放 list 下的节点

  // 遍历 list
  for (const item of list) {
    // 1. 获取节点的 id 和 父 id
    const { id, parent_id } = item; // ES6 解构赋值

    // 2. 将节点存入 map
    if (!map[id]) map[id] = {};

    // 3. 根据 id，将节点与之前存入的子节点合并
    map[id] = map[id].children
      ? { ...item, children: map[id].children }
      : { ...item };

    // 4. 如果是根节点，存入 result
    if (parent_id === root) {
      result.push(map[id]);
    } else {
      // 5. 反之，存入父节点
      if (!map[parent_id]) map[parent_id] = {};
      if (!map[parent_id].children) map[parent_id].children = [];
      map[parent_id].children.push(map[id]);
    }
  }

  // 将结果返回
  return result;
}