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

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

一、扁平数组转树形结构

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

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 data) {
    itemMap[item.id] = { ...item, children: [] }
    const id = item.id;
    const pid = item.pid;
    const treeItem = itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      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
}