如何根据选中分类ID向上追溯父类生成指定顺序数组？

我有一个包含id和parentId的分类列表，每个分类的parentId对应另一个分类的id。现在需要实现：当选中某一分类（比如ID为10的分类）时，生成一个新数组——第一个元素是选中的分类，之后依次添加它的父分类，直到parentId为0的根分类为止。

示例数据 #

let arr = [
  { title: 'category 1', id: 1, parentId: 0},
  { title: 'category 2', id: 2, parentId: 1},
  { title: 'category 3', id: 3, parentId: 4},
  { title: 'category 4', id: 4, parentId: 2},
  { title: 'category 5', id: 5, parentId: 3},
  { title: 'category 6', id: 6, parentId: 2},
  { title: 'category 7', id: 7, parentId: 5},
  { title: 'category 8', id: 8, parentId: 0},
  { title: 'category 9', id: 9, parentId: 0},
  { title: 'category 10', id: 10, parentId: 6},
]

预期结果 #

选中ID为10的分类后，得到的数组：

let resultArr = [
  { title: 'category 10', id: 10, parentId: 6},
  { title: 'category 6', id: 6, parentId: 2},
  { title: 'category 2', id: 2, parentId: 1},
  { title: 'category 1', id: 1, parentId: 0},
]

解决方案 #

方法一：对象映射优化查找（适合大数据量）

先把分类数组转换成以id为键的对象映射，将每次查找父分类的时间复杂度降到O(1)，整体性能更优：

function getCategoryChain(categories, targetId) {
  // 构建id到分类对象的映射表
  const categoryMap = categories.reduce((map, item) => {
    map[item.id] = item;
    return map;
  }, {});

  const chain = [];
  let currentId = targetId;

  // 循环向上查找直到根节点（parentId为0）
  while (currentId !== 0) {
    const currentCategory = categoryMap[currentId];
    if (!currentCategory) break; // 处理找不到对应分类的异常情况
    chain.push(currentCategory);
    currentId = currentCategory.parentId;
  }

  return chain;
}

// 调用示例
const targetChain = getCategoryChain(arr, 10);
console.log(targetChain);

方法二：直接数组查找（适合小数据量）

如果分类数组数据量较小，也可以直接用find方法循环查找父分类：

function getCategoryChain(categories, targetId) {
  const chain = [];
  let currentId = targetId;

  while (currentId !== 0) {
    const currentCategory = categories.find(item => item.id === currentId);
    if (!currentCategory) break;
    chain.push(currentCategory);
    currentId = currentCategory.parentId;
  }

  return chain;
}

// 调用示例
const targetChain = getCategoryChain(arr, 10);
console.log(targetChain);

说明 #

两种方法都会从目标分类开始，依次向上遍历父级分类，直到找到parentId为0的根节点为止，最终生成的数组顺序为「目标分类 → 直接父分类 → ... → 根分类」。第一种方法的映射表优化更适合数据量较大的场景，能避免频繁遍历数组带来的性能损耗。

内容的提问来源于stack exchange，提问作者tako-sphynx