数组转树形结构

问题

将带有 id 和 parentId 的扁平数组转换为嵌套的树形结构。

// 输入
const list = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 1 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 2 },
  { id: 5, name: '部门E', parentId: 3 },
]

// 输出
[
  {
    id: 1,
    name: '部门A',
    parentId: 0,
    children: [
      { id: 2, name: '部门B', parentId: 1, children: [
        { id: 4, name: '部门D', parentId: 2, children: [] }
      ]},
      { id: 3, name: '部门C', parentId: 1, children: [
        { id: 5, name: '部门E', parentId: 3, children: [] }
      ]}
    ]
  }
]

解答

方法一：两次遍历（Map 映射）

function arrayToTree(list, rootId = 0) {
  // 第一次遍历：创建 id -> node 的映射
  const map = new Map()
  list.forEach(item => {
    map.set(item.id, { ...item, children: [] })
  })

  const result = []

  // 第二次遍历：建立父子关系
  list.forEach(item => {
    const node = map.get(item.id)
    if (item.parentId === rootId) {
      // 根节点直接放入结果
      result.push(node)
    } else {
      // 找到父节点，添加到其 children 中
      const parent = map.get(item.parentId)
      if (parent) {
        parent.children.push(node)
      }
    }
  })

  return result
}

方法二：一次遍历

function arrayToTree(list, rootId = 0) {
  const map = new Map()
  const result = []

  list.forEach(item => {
    // 获取或创建当前节点
    const node = map.get(item.id) || { children: [] }
    // 合并数据
    Object.assign(node, item)
    map.set(item.id, node)

    if (item.parentId === rootId) {
      result.push(node)
    } else {
      // 获取或创建父节点
      const parent = map.get(item.parentId) || { children: [] }
      map.set(item.parentId, parent)
      parent.children.push(node)
    }
  })

  return result
}

方法三：递归

function arrayToTree(list, parentId = 0) {
  return list
    .filter(item => item.parentId === parentId)
    .map(item => ({
      ...item,
      children: arrayToTree(list, item.id)
    }))
}

测试

const list = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 2, name: '部门B', parentId: 1 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 2 },
  { id: 5, name: '部门E', parentId: 3 },
]

console.log(JSON.stringify(arrayToTree(list), null, 2))

关键点

• Map 映射：用 Map 存储 id 到节点的映射，实现 O(1) 查找
• 时间复杂度：两次遍历和一次遍历都是 O(n)，递归是 O(n²)
• 处理顺序：一次遍历法不依赖数组顺序，父节点可以在子节点之后出现
• 递归简洁但性能差：每次递归都要遍历整个数组，数据量大时不推荐
• 注意引用关系：Map 存储的是对象引用，修改会同步到结果中