0. 前言

数组的结构如下，其中id 为当前项， pid 为当前项的父项 id 。

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

本节讨论的问题是如何将上述数组结构转化成树结构。

一般解决问题的思路有两个：递归与非递归版本。

1. 使用递归解决

对于递归问题，根据五点七边 (opens new window) 的算法理论，可以将递归问题划分为 微操作 与超级操作。

对本题而言：

• 超级操作：完成 pid 项的树形结构构造。

  树形结构的特点是：引用地址套引用地址。

  因此在构造树形结构的超级操作函数时，除了有原始数据 originData、标识当前操作层数的 pid 项，还有一个非常重要的参数，借用上一层的引用地址 mountPoint（数组）。

• 微操作：

  1. 根据 pid 项，找到需要被挂载的 item
  2. 将 item 向上挂载到 父item：此时就要求超级操作，需要暴露出一个父 item 的引用地址（mountPoint）
  3. 将 item 向下挂载（当前 item 已完成树形结构的拼接）：再调用一次超级操作。

  上述步骤中 2、3 的次序不是很重要，因为引用地址（children）一旦创建就已经确定，至于指引定制内的内容（children 数组内的内容）可以调用超级操作实现。

// 本题的难点
// originData 原始数据，mountPoint 挂载点，pid 父元素
function getChildren(originData, mountPoint, pid) {
  const curItem = originData.find(item => item.pid === pid);
  if (curItem) {
    const newItem = { ...curItem, children: [] };
    // 一次塔罗：将 pid 对应的 item 挂载在 mountPoint 上。
    mountPoint.push(newItem);
    // 树结构的指针移动
    getChildren(originData, newItem.children, curItem.id);
  }
}

function arrayToTree(originData, rootId) {
  const result = [];
  getChildren(originData, result, rootId);
  return result;
}

arrayToTree(arr, 0);

自顶向下进行挂载处理：

// 设计汉诺塔函数：originData 操作数据能力
// pid 某种程度起到的是指针的作用
function arrayToTree(originData, pid) {
  return originData
    .filter(item => item.pid === pid)
    .map(item => ({
      ...item,
      children: arrayToTree(originData, item.id),
    }));
}
arrayToTree(arr, 0);

非递归版本

增加空间复杂度，基于 id 去生成一个 key-value 结构。

示例代码使用的是 ：Map

function arrayToTree(data, rootId) {
  const result = [];
  const itemMap = new Map();

  /* 构造临时变量 */
  for (const item of data) {
    /* 以 id 作为 key - value */
    itemMap.set(item.id, { ...item, children: [] });
  }
  for (const item of data) {
    const id = item.id;
    const pid = item.pid;
    const treeItem = itemMap.get(id);
    /* 处理根节点 */
    if (pid === rootId) {
      /* 直接存入 */
      result.push(treeItem);
    } else {
      /* 处理尾节点 */
      if (!itemMap.get(pid)) {
        itemMap.set(pid, { children: [] });
      }
      itemMap.get(pid).children.push(treeItem);
    }
  }
}

扩展

在算法场景下典型的递归问题有：

1. 汉诺塔问题。
2. 归并问题。

然后我发现本题的解决思路为 验证回文串 的写法树形版本。