让我们假设我们有一个由字典组成的列表，该列表中的每个字典都包含一个表示父节点的键。这是这个列表的极度简化版本。请注意：

• 顺序无关。因此“孙辈”可能先出现。
• 子节点只了解父节点。

list = [{"name" : "a" }, {"name" : "b", "parent" : "a" },{"name" : "c", "parent" : "b" }]

我想要实现的是创建一个新的列表或对象，其子节点嵌套在父节点里面。大致会是这样的。请注意一个父节点可以有多个子节点。

a_new_list =[

{"name" : "a", "children" : [

{"name" : "b", "parent" : "a", "children" : [

{"name" : "c", "parent" : "b" }

]}

]}

]

我该如何以一种最终能够按层级将所有孙辈分组的方式遍历这个列表？

我尝试过使用一些相当笨拙的方法（包括在信息为扁平时添加“层级”，以及使用类来构建层次化对象，但在检查孙辈时彻底失败）

解决方案

一个相当简单的递归函数：

def f(nodes: list[dict], parent: str = None):
    current_level_nodes = []

    for node in nodes:
        if node.get('parent') == parent:
            node_copy = node.copy()  # copying since we'll modify it

            children = f(nodes, node_copy['name'])
            if children:
                node_copy['children'] = children

            current_level_nodes.append(node_copy)

    return current_level_nodes

用法如下：

>>> l = [{"name" : "a" }, {"name" : "b", "parent" : "a" },{"name" : "c", "parent" : "b" }]
>>> f(l)
[{'name': 'a', 'children': [{'name': 'b', 'parent': 'a', 'children': [{'name': 'c', 'parent': 'b'}]}]}]

该操作很简单：

• 用扁平的节点列表和当前父节点来调用该函数
• 该函数将在列表中查找所有父节点为给定父节点的节点
• 初始时，父节点是 None，因此会返回顶层节点
• 对于每个找到的节点，通过递归调用函数来查找它的子节点，将该节点的名称作为父参数传入，并把子节点添加到该节点中

这可以进行优化，使整个节点列表不需要一次又一次地遍历，但为了演示算法的目的，我就不去处理这类复杂性；只有在你要处理非常长的列表时才会需要。