请求实现：基于带层级前缀的分类数组生成ID对应层级路径的算法

问题描述 #

给定API返回的商品分类数组（结构如下），需要实现一个接收$id参数的函数，返回对应ID的完整层级路径：

• 传入主分类ID，返回分类名
• 传入子分类ID，返回「主分类 > 子分类」
• 传入子子分类ID，返回「主分类 > 子分类 > 子子分类」

示例数组：

$categories = [
    1 => 'CATEGORY 1',
    2 => '-Subcat 1',
    9 => '-Subcat 2',
    12 => '-Subcat 3',
    13 => '-Subcat 4',
    46 => '-Subcat 5',
    47 => '-Subcat 6',
    3 => 'CATEGORY 2',
    4 => '-Subcat 1',
    68 => '-Subcat 2',
    69 => '-Subcat 3',
    154 => '-Subcat 4',
    5 => 'CATEGORY 3',
    6 => '-Subcat 1',
    7 => '-Subcat 2',
    76 => '--Subsubcat 1',
    156 => '--Subsubcat 2',
    157 => '--Subsubcat 3',
    10 => '-Subcat 3',
    11 => '-Subcat 4',
    20 => '-Subcat 5',
    54 => '-Subcat 6',
    55 => '-Subcat 7',
    56 => '--Subsubcat 1',
    60 => '--Subsubcat 2',
    65 => '--Subsubcat 3',
    74 => '--Subsubcat 4',
    61 => '-Subcat 8'
];

算法实现思路 #

1. 预处理分类数据：遍历数组，为每个分类ID记录三个关键信息：

   • 清理前缀后的分类名称（去掉开头的-或--）
   • 当前分类的层级（0=主分类，1=子分类，2=子子分类）
   • 父分类ID
     遍历过程中维护一个层级追踪栈，确保每个子分类/子子分类能关联到最近的父节点：
   • 遇到主分类（无前缀）时，更新层级0的父节点，清空层级1、2的追踪
   • 遇到子分类（1个-前缀）时，关联最近的主分类为父节点，更新层级1的追踪
   • 遇到子子分类（2个-前缀）时，关联最近的子分类为父节点

2. 生成层级路径：根据目标ID，从预处理的记录中向上回溯所有父节点，收集名称后反转顺序，用>拼接成最终路径。

代码实现 #

function getCategoryPath($id, $categories) {
    // 预处理分类数据，存储每个ID的名称、层级、父ID
    $categoryMeta = [];
    // 追踪当前各层级的活跃父节点：index 0=主分类，1=子分类
    $activeParents = [null, null];

    foreach ($categories as $catId => $name) {
        // 计算前缀数量，确定层级
        $dashCount = strspn($name, '-');
        $cleanName = ltrim($name, '-');
        $level = $dashCount;

        $parentId = null;
        if ($level === 0) {
            // 主分类，无父节点，更新层级0的活跃父节点
            $activeParents[0] = $catId;
            // 清空子分类层级的追踪
            $activeParents[1] = null;
        } elseif ($level === 1) {
            // 子分类，父节点是最近的主分类
            $parentId = $activeParents[0];
            // 更新层级1的活跃父节点
            $activeParents[1] = $catId;
        } elseif ($level === 2) {
            // 子子分类，父节点是最近的子分类
            $parentId = $activeParents[1];
        }

        $categoryMeta[$catId] = [
            'name' => $cleanName,
            'parent_id' => $parentId,
            'level' => $level
        ];
    }

    // 检查目标ID是否存在
    if (!isset($categoryMeta[$id])) {
        return ''; // 或抛出异常，根据需求处理
    }

    // 回溯收集路径
    $path = [];
    $currentId = $id;
    while ($currentId !== null) {
        $path[] = $categoryMeta[$currentId]['name'];
        $currentId = $categoryMeta[$currentId]['parent_id'];
    }

    // 反转路径并拼接
    return implode(' > ', array_reverse($path));
}

// 测试示例
echo getCategoryPath(65, $categories); // 输出：CATEGORY 3 > Subcat 7 > Subsubcat 3
echo getCategoryPath(55, $categories); // 输出：CATEGORY 3 > Subcat 7
echo getCategoryPath(5, $categories);  // 输出：CATEGORY 3

代码说明 #

• 预处理阶段只需要执行一次，如果多次调用函数，可以将$categoryMeta缓存起来，避免重复遍历数组
• 对于不存在的ID，函数返回空字符串，可根据实际需求修改为抛出异常或返回提示信息
• 层级判断通过统计开头-的数量实现，完全适配API返回的格式规则

内容的提问来源于stack exchange，提问作者Faye D.