如何将一个普通一维数组转换成一个树形结构？

angrybird2332023-04-22Frontend面试

题目：现有这样一个数组，如何把它转换成一个树形结构的数组？顶部只有一个根节点

const list = [
  { id: 1, parentId: 0 },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 2 },
  { id: 4, parentId: 3 },
  { id: 5, parentId: 4 },
  { id: 6, parentId: 5 },
  { id: 7, parentId: 6 },
  { id: 8, parentId: 7 },
  { id: 9, parentId: 8 },
]

1. 创建一个空对象，用于存储节点及其子节点的关系。这将作为查找父节点和快速构建树形结构的辅助数据结构。
1. 遍历输入数组，为每个节点创建一个映射项，并将其添加到nodeMap中。这样可以方便地通过id访问节点，并为其初始化子节点数组。
1. 再次遍历输入数组，对于每个节点，找到其在nodeMap中的父节点，然后将当前节点添加到父节点的children数组中。
1. 从nodeMap中提取根节点。根节点具有parentId为0的特性。将这些节点放入一个新的数组中，即为所需树形结构数组。代码如下：

const nodeMap = {};

for (const item of list) {
  nodeMap[item.id] = { ...item, children: [] };
}

for (const item of list) {
  const parent = nodeMap[item.parentId];
  if (parent) {
    parent.children.push(nodeMap[item.id]);
  }
}

const tree = Object.values(nodeMap).filter((node) => node.parentId === 0);

封装成函数如下：

function convertToTree(list) {
  const nodeMap = {};
  for (const item of list) {
    nodeMap[item.id] = { ...item, children: [] };
  }
  for (const item of list) {
    const parent = nodeMap[item.parentId];
    if (parent) {
      parent.children.push(nodeMap[item.id]);
    }
  }
  const tree = Object.values(nodeMap).filter((node) => node.parentId === 0);
  return tree
}