js扁平数组和树形结构互相转化

面试中一道常见的算法题，扁平数组结构与树形结构互相转换如何实现?

一、扁平数组转树形结构

扁平数组转树形结构可以通过递归实现，但是为了实现时间复杂度、空间复杂度最优，该选用什么方法呢?

var data = [
  { id: 1, pid: 0, name: '超市' },
  { id: 2, pid: 0, name: '生鲜区' },
  { id: 3, pid: 1, name: '零食区' },
  { id: 4, pid: 2, name: '大虾' },
  { id: 5, pid: 2, name: '猪肉' },
  { id: 6, pid: 13, name: '卫生纸' },
  { id: 7, pid: 3, name: '薯片' },
  { id: 8, pid: 7, name: '烧烤味' },
  { id: 9, pid: 7, name: '黄瓜味' }
];

1、递归

该实现的时间复杂度为O(2^n)，并不是最优的方案具体思路如下：

• 定义一个空数组data，放置修改后的数据
• 遍历原数组，将数组中每一项的pid与根pid（案例中的pid为 0，直接传进来的数据）进行比较
• 为每一项增加children属性
• children项数据需要递归原数据，并且把该项的id传过去，当作该项的根pid
• 把data返回

function recurrenceFilter(arr, pid) {
  let data = [];
  arr.forEach(item => {
    if (item.pid === pid && item.pid===0) {
      item.children = recurrenceFilter(arr, item.id)
      data.push(item)
    }
  });
  return data
}
console.log(recurrenceFilter(data, 0))

结果如下：

[
  {
    "id": 1,
    "pid": 0,
    "name": "超市",
    "children": [
      {
        "id": 3,
        "pid": 1,
        "name": "零食区",
        "children": [
          {
            "id": 7,
            "pid": 3,
            "name": "薯片",
            "children": [
              { "id": 8, "pid": 7, "name": "烧烤味", "children": [] },
              { "id": 9, "pid": 7, "name": "黄瓜味", "children": [] }
            ]
          }
        ]
      }
    ]
  },
  {
    "id": 2,
    "pid": 0,
    "name": "生鲜区",
    "children": [
      { "id": 4, "pid": 2, "name": "大虾", "children": [] },
      { "id": 5, "pid": 2, "name": "猪肉", "children": [] }
    ]
  }
]

2、将数据转成 Map 存储再进行处理

将数据转成 Map 存储再进行处理，根据如下代码可知，实现结构转变只需要循环一次，并且这种方式的时间复杂度为O(n) ，空间复杂度为O(n)，比递归的性能要好很多，我们项目中肯定是追求性能最优。具体实现思路如下：

• 声明一个空数组 result 存放结果，声明一个 Map 对象存放以id为key，以{ ...item, children: [] }为value的数据
• 对数组for...of 循环
• 循环中，itemMap存储数据 Map 数据，并为每一项创建 children 属性
• pid 为 0 说明是根数据，把 pid 为 0 的这一项放到 result 中
• pid 不为 0 说明该项为子数据且已存在父级数据（因为itemMap(pid)存在），所以只需要把该项数据 push 到父级数据的 children 属性。

代码如下：

function recurrenceFilter(data) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
  for (const item of items) {
    itemMap[item.id] = { ...item, children: [] }
    const id = item.id;
    const pid = item.pid;
    const treeItem = itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

3、使用 new Map()处理数据

2 中我们使用用id为key，数组中每项为value，以此存储 Map 类型数据。我们也可以直接使用new Map()生成一个 Map 实例来存储数据，可以通过 set 设置数据，get 获取数据。其中使用了new Object()，为浅克隆，含义为创建一个用户定义的对象类型的实例或具有构造函数的内置对象的实例。

function recurrenceFilter(data) {
  var result = [];//存储结果
  var map = new Map(); //存在 id,对应所在的内存地址
  var tempObj, pid;
  for (let i = 0; i < data.length; i++) {
    pid = data[i].pid;
    //map 中存在 pid
    if (map.has(pid)) {
      //存在 pid 则将些信息加入到对应 id=pid 的对象上的 children
      // pid 这项是否存在 children
      if (!map.get(pid).children)        
          map.get(pid).children = [];
      var obj = new Object(data[i]);
      map.get(pid).children.push(obj);
      map.set(data[i].id, obj);
    } else if (!map.has(pid) && pid == 0) {
      //处理 pid 不存在且 pid 为 0 的情况
      // 1.将该项 push 到 result
      // 2. id 为 key，该项对象为 value 存储
      tempObj = new Object(data[i]);
      result.push(tempObj);
      map.set(data[i].id, tempObj);
    }
  }
  return result;
}

二、树形结构转扁平数组

树形结构层级未知，故需要递归循环数据。

• 解构每一项 item
• 除了 children 的属性外其他元素 push 数组
• children 长度不为 0 则递归循环

代码如下：

function flattenArr(tree, arr = []) {
  tree.forEach(item => {
    // 结构 item
    const { children, ...props } = item;
    // 添加除了 children 的属性
    arr.push(props);
    if (children.length!=0) {
      // 存在 children 递归将所有节点加入到结果集中
      flattenArr(children, arr);
    }
  })
  return arr;
}