数组转为树

期望

输入值

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

期望转换后的输出值

[
  {
    "id": 1,
    "name": "部门1",
    "pid": 0,
    "children": [
      {
        "id": 2,
        "name": "部门2",
        "pid": 1,
        "children": []
      },
      // ...
    ]
  }
]

实现

可以使用时间复杂度为 O(n) 的实现，只对数组进行一次遍历就可进行转换

interface Item {
  id: number
  name: string
  pid: number
}

interface ItemTree {
  id: number
  name: string
  pid: number
  children: ItemTree[]
}

function arrayToTree(items: Item[]): ItemTree[] {
  const result = []; // 存储结果
  const itemMap = {}; // 存储中间值
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      };
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children'],
    };

    const treeItem = itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        };
      }
      itemMap[pid].children.push(treeItem);
    }
  }
  return result;
}