Python中将扁平分类层级数据转换为层级数据的最优方案

嘿，这个需求我之前处理过好多次，最靠谱高效的方法就是用哈希表做节点映射，两次遍历搞定，时间复杂度O(n)，绝对是最优解。下面给你详细拆解：

核心思路 #

要把扁平结构转层级，关键是快速找到每个节点的父节点。我们可以先把所有节点用id作为键存到一个字典里（O(1)查找），然后遍历每个节点，把它挂载到对应父节点的children列表中；没有父节点的就是顶级节点，直接加入结果列表。

代码实现 #

def flat_to_hierarchy(categories):
    # 第一步：构建id到节点的映射，同时给每个节点初始化children列表
    node_map = {}
    for cat in categories:
        # 复制原字典，避免修改原始数据
        node = cat.copy()
        node['children'] = []
        node_map[cat['id']] = node
    
    # 第二步：遍历所有节点，挂载到对应的父节点下
    hierarchy = []
    for node in node_map.values():
        parent_id = node['parent_category_id']
        if parent_id is None:
            # 没有父节点，属于顶级分类
            hierarchy.append(node)
        else:
            # 找到父节点，将当前节点加入其子列表
            # 可选：加个判断避免无效parent_id导致KeyError
            if parent_id in node_map:
                node_map[parent_id]['children'].append(node)
    
    return hierarchy

测试示例 #

用你提供的数据集（补全category6和7）测试：

d = [
    {'id': 1, 'name': 'category1', 'parent_category_id': None, 'level': 1},
    {'id': 2, 'name': 'category2', 'parent_category_id': None, 'level': 1},
    {'id': 3, 'name': 'category3', 'parent_category_id': None, 'level': 1},
    {'id': 4, 'name': 'category4', 'parent_category_id': 1, 'level': 2},
    {'id': 5, 'name': 'category5', 'parent_category_id': 1, 'level': 2},
    {'id': 6, 'name': 'category6', 'parent_category_id': 4, 'level': 3},
    {'id': 7, 'name': 'category7', 'parent_category_id': 5, 'level': 3}
]

result = flat_to_hierarchy(d)

# 格式化输出查看层级结构
import json
print(json.dumps(result, indent=2))

输出结果会是清晰的层级结构：

[
  {
    "id": 1,
    "name": "category1",
    "parent_category_id": null,
    "level": 1,
    "children": [
      {
        "id": 4,
        "name": "category4",
        "parent_category_id": 1,
        "level": 2,
        "children": [
          {
            "id": 6,
            "name": "category6",
            "parent_category_id": 4,
            "level": 3,
            "children": []
          }
        ]
      },
      {
        "id": 5,
        "name": "category5",
        "parent_category_id": 1,
        "level": 2,
        "children": [
          {
            "id": 7,
            "name": "category7",
            "parent_category_id": 5,
            "level": 3,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "id": 2,
    "name": "category2",
    "parent_category_id": null,
    "level": 1,
    "children": []
  },
  {
    "id": 3,
    "name": "category3",
    "parent_category_id": null,
    "level": 1,
    "children": []
  }
]

为什么这是最优解？ #

• 时间效率：两次线性遍历，加上哈希表的O(1)查找，整体时间复杂度是O(n)，不管数据集多大都能快速处理。
• 空间效率：额外用了一个字典存储节点映射，空间复杂度O(n)，这是合理的 trade-off。
• 鲁棒性：不依赖原始数据的排序顺序，不管节点是按什么顺序排列的都能正确生成层级。
• 可维护性：代码逻辑清晰，容易理解和修改，比如可以快速添加对无效父ID的处理、自定义字段名等。

不推荐的方法：递归查找 #

有些同学会想到用递归：先找所有顶级节点，然后对每个顶级节点递归查找它的子节点。但这种方法每次找子节点都要遍历整个列表，时间复杂度是O(n²)，当数据量较大时（比如上千个节点），性能会差很多，而且如果层级极深还可能触发递归栈溢出，所以不推荐作为最优方案。

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