数组转树的写法，求指教？

Question

给定：

const source = [
  { id: 19, parentId: 0 },
  { id: 18, parentId: 16 },
  { id: 17, parentId: 16 },
  { id: 16, parentId: 0 },
  { id: 15, parentId: 17 },
  { id: 14, parentId: 19 },
  { id: 21, parentId: 19 },
  { id: 20, parentId: 18 },
]

输出样例：

{
  "id": 0,
  "children": [
    {
      "id": 19,
      "parentId": 0,
      "children": [
        {
          "id": 14,
          "parentId": 19
        },
        {
          "id": 21,
          "parentId": 19
        }
      ]
    },
    {
      "id": 16,
      "parentId": 0,
      "children": [
        {
          "id": 18,
          "parentId": 16,
          "children": [
            {
              "id": 20,
              "parentId": 18
            }
          ]
        },
        {
          "id": 17,
          "parentId": 16,
          "children": [
            {
              "id": 15,
              "parentId": 17
            }
          ]
        }
      ]
    }
  ]
}

求一份解答。

Answer 1

这样？

js 代码

source.reduce((o, i) => {
  i = Object.assign(o[i.id] ??= {}, i);
  ((o[i.parentId] ??= {}).children ??= []).push(i);
  return o;
}, {0: {id: 0}})[0]

结果

{
  "id": 0,
  "children": [
    {
      "id": 19,
      "parentId": 0,
      "children": [
        {
          "id": 14,
          "parentId": 19
        },
        {
          "id": 21,
          "parentId": 19
        }
      ]
    },
    {
      "children": [
        {
          "id": 18,
          "parentId": 16,
          "children": [
            {
              "id": 20,
              "parentId": 18
            }
          ]
        },
        {
          "id": 17,
          "parentId": 16,
          "children": [
            {
              "id": 15,
              "parentId": 17
            }
          ]
        }
      ],
      "id": 16,
      "parentId": 0
    }
  ]
}

Answer 2

一个暴力实现，需要优化：

interface T {
    id: number
    parentId?: number
    children?: T[]
}

const vals = [
    { id: 19, parentId: 0 },
    { id: 18, parentId: 16 },
    { id: 17, parentId: 16 },
    { id: 16, parentId: 0 },
    { id: 15, parentId: 17 },
    { id: 14, parentId: 19 },
    { id: 21, parentId: 19 },
    { id: 20, parentId: 18 }
];

const build = (vals: T[]) => {
    const dfs = (parentId: number) => {
        const res: T[] = []
        for (const v of vals) {
            if (v.parentId === parentId) {
                res.push({
                    ...v,
                    children: dfs(v.id)
                })
            }
        }
        return res
    }
    return {
        id: 0,
        children: dfs(0)
    }
}

Answer 3

在面试中比较常见，一种较优的解法：

// 扁平数组转换成树结构
function arr2Tree(list) {
  const result = []
  // 收集所有项：id为key，对应值为value
  const dp = list.reduce((prev, curr) => {
    prev[curr.id] = curr
    return prev
  }, {})

  for (item of list) {
    // 收集所有根节点
    if (item.parentId === 0) {
      result.push(item)
      continue
    }

    // 找到当前节点的父节点，并放入到它的子节点中
    if (dp[item.parentId]) {
      if (!dp[item.parentId].children) {
        dp[item.parentId].children = []
      }
      dp[item.parentId].children.push(item)
    }
  }
  return result
}