扁平化数组与树形结构的互相转换

写在前面

​ 今天在做项目的时候，遇到了需要将扁平化数组转换成树形结构的问题。首先第一个想到的是用递归去处理，但是在实际应用的时候，一旦数组长度比较大的时候，性能十分不理想（时间复杂度为0(n^2)，能理想就怪了）。后面在查阅资料的时候，发现有更优解，特此记录下来。

​ 先看一下数据：

扁平化数组：

let arr = [
  { id: 5, name: "5", pid: 4 },
  { id: 1, name: "1", pid: 0 },
  { id: 2, name: "2", pid: 1 },
  { id: 3, name: "3", pid: 1 },
  { id: 4, name: "4", pid: 3 },
];

树形结构

let tree = [
  {
    id: 1,
    name: 1,
    pid: 0,
    children: [
      {
        id: 2,
        name: 2,
        pid: 1,
        children: [],
      },
      {
        id: 3,
        name: 3,
        pid: 1,
        children: [
          {
            id: 4,
            name: 4,
            pid: 3,
            children: [{ id: 5, name: 5, pid: 4, children: [] }],
          },
        ],
      },
    ],
  },
];

扁平化数组→树形结构(array to tree)

递归方式

/**
 * @description: 
 * @param {*} items 数组
 * @param {*} rootId 根节点id
 * @return {*}
 */
function array2tree(items,rootId) {
  let res = []
  let getChildren = (res, rootId) => {
    for(const i of items) {
      if(i.pid === rootId) {
        const newItem = {...i, children: []}
        res.push(newItem)
        getChildren(newItem.children,newItem.id)
      }
    }
  }
  getChildren(res, rootId)
  return res
}

其实思路也很简单，首先传入数组items和根节点ID，然后遍历数组，找到与根节点下的子节点，把子节点push到父节点的children数组里面。然后递归这个过程。。。

显然，这个算法的时间复杂度为O(n^2)

非递归方式

/**
 * @description: 
 * @param {*} items 数组
 * @param {*} rootId 根节点id
 * @return {*}
 */
function array2tree(items, rootId) {
  const result = []; // 存放结果集
  const map = {}; // 暂存数组以id为key的映射关系

  // 先转成map存储
  for (const item of items) {
    map[item.id] = { ...item, children: [] };
  }

  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem = map[id];
    if (pid === rootId) {
      // 根节点
      result.push(treeItem);
    } else {
      // 非根节点
      if (!map[pid]) {
        // 如果父节点不存在，则初始化父节点(处理第一个节点不是根节点的情形)
        map[pid] = {
          children: [],
        };
      }
      // 将节点push到对应父节点下
      map[pid].children.push(treeItem);
    }
  }
  return result;
}

这里说一下思路，先把数组转成以id为key的映射关系。然后再遍历一次数组存入根节点，借助对象的引用，只需要更新map中的children即可。具体可看下面的流程图

显然，时间复杂度为O(n)

最佳性能

/**
 * @description: 
 * @param {*} items 数组
 * @param {*} rootId 根节点id
 * @return {*}
 */
function array2tree(items, rootId) {
  const res = []; // 存放结果集
  const map = {}; //
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!map[id]) {
      map[id] = {
        children: [],
      };
    }
    map[id] = {
      ...item,
      children: map[id].children,
    };
    // 不可以像之前一样写成map[id] = {...item, children: [] }，因为节点有可能在找不到parent的时候存入map中

    const treeItem = map[id];

    if (pid === rootId) {
      res.push(treeItem);
    } else {
      if (!map[pid]) {
        map[pid] = {
          children: [],
        };
      }
      map[pid].children.push(treeItem);
    }
  }
  return res;
}

边做map存储，边找对应关系

显然，时间复杂度为O(n)

树形数据→扁平化数组(tree to array)

递归实现

/**
 * @description: 
 * @param {*} items 树形数据
 * @return {*}
 */
function tree2arr(items) {
  let res = []; // 存放结果集

  items.forEach((item) => {
    // children为字节点数组， node存放节点数据
    const { children, ...node } = item;
    res.push(node);
    if (children && children.length) {
      res = res.concat(tree2arr(children));
    }
  });
  return res;
}

遍历tree，每一项加进结果集，如果有children且长度不为0，则递归遍历

显然时间复杂度为O(n^2)

总结

Array To Tree

递归方式：每次递归寻找当前节点的子节点，并且需要重新遍历数组，时间复杂度为O(n^2)

非递归方式：利用对象的保存是引用这个特点，通过map保存节点及其子节点的信息，只需要将根节点存入数组，即可得到整个树形数据。时间复杂度是O(n)