如何将同数组中的多级子分类嵌套到对应父分类结构中？

需求背景 #

开发带多级子分类的下拉菜单，后端返回包含parent_id属性的分类数组（parent_id为null表示主分类），需要将其转换为支持任意层级的嵌套结构，现有代码仅能处理两级分类，无法适配更深层级的子分类。

后端返回的分类数组 #

const categories = [
  { id: "10001", name: "name1", parent_id: null },
  { id: "10002", name: "name2", parent_id: "10001" },
  { id: "10003", name: "name3", parent_id: "10001" },
  { id: "10004", name: "name4", parent_id: null },
  { id: "10005", name: "name5", parent_id: null },
  { id: "10006", name: "name6", parent_id: "10002" },
  { id: "10007", name: "name7", parent_id: "10002" },
  { id: "10008", name: "name8", parent_id: "10003" },
  { id: "10009", name: "name9", parent_id: "10004" },
]

期望的嵌套结构 #

const categories= [
  {
    id: "10001",
    name: "name1",
    subCategories: [
      {
        id: "10002",
        name: "name2",
        subCategories: [
          { id: "10006", name: "name6" },
          { id: "10007", name: "name7" },
        ],
      },
      {
        id: "10003",
        name: "name3",
        subCategories: [{ id: "10008", name: "name8" }],
      },
    ],
  },
  {
    id: "10004",
    name: "name4",
    subCategories: [{ id: "10009", name: "name9" }],
  },
  { id: "10005", name: "name5" , subCategories: [] },
]

现有代码问题 #

现有代码仅能处理两级分类，无法递归生成更深层级的子分类：

const result = categories
  .map((category, index, array) => {
    if (category.parent_id === null) {
      return {
        ...category,
        subCategory: array.filter((cat) => cat.parent_id === category.id),
      }
    }
    return null; // insert null in array
  })
  .filter((category) => category); // filter null items from array

解决方案 #

实现思路 #

1. 构建分类映射表，以分类id为键、分类对象为值，快速定位父分类；
2. 遍历所有分类，将子分类挂载到对应父分类的subCategories数组中；
3. 收集所有parent_id为null的主分类，得到最终嵌套结构。

代码实现 #

function buildNestedCategories(categories) {
  // 初始化映射表，给每个分类添加subCategories数组
  const categoryMap = {};
  categories.forEach(category => {
    categoryMap[category.id] = {
      ...category,
      subCategories: []
    };
  });

  const nestedCategories = [];
  categories.forEach(category => {
    const current = categoryMap[category.id];
    if (category.parent_id === null) {
      // 主分类直接加入结果数组
      nestedCategories.push(current);
    } else {
      // 将当前分类挂载到父分类的subCategories中
      const parent = categoryMap[category.parent_id];
      parent?.subCategories.push(current);
    }
  });

  return nestedCategories;
}

// 使用示例
const nestedCategories = buildNestedCategories(categories);
console.log(nestedCategories);

代码说明 #

• 映射表将父分类查找的时间复杂度降至O(1)，整体算法时间复杂度为O(n)，效率更高；
• 支持任意深度的分类嵌套，不受层级限制；
• 自动初始化subCategories数组，避免出现未定义的情况。

内容的提问来源于stack exchange，提问作者pooya