获取树状字典列表各分支最深层级最大值对应节点

现有一个表示树形结构的字典列表，其中level字段代表节点层级（如level 1节点是level 0节点的子节点，依此类推），具体数据如下：

list_of_dicts = [{'name': 'Parent', 'number': 1299, 'level': 0}, 
{'name': 'A', 'number': 1011, 'level': 1}, 
{'name': 'B', 'number': 789, 'level': 2}, 
{'name': 'C', 'number': 430, 'level': 3},
{'name': 'D', 'number': 300, 'level': 2}, 
{'name': 'E', 'number': -100, 'level': 3},
{'name': 'F', 'number': 74, 'level': 2}, 
{'name': 'G', 'number': 300, 'level': 1}, 
{'name': 'H', 'number': 140, 'level': 2}]

需求：编写函数提取每个父节点分支下最深层级中number值最大的节点名称。本示例预期输出为：

expected = ["C", "H"]

原因：A分支最深层级为level 3，C的number值最大；G分支最深层级为level 2，H的number值最大

用户尝试的实现方案无法得到正确结果：

def extract_max_values(data):
    max_values = {}
    
    for item in data:
        node_name = item['name']
        node_number = item['number']
        node_level = item['level']
        
        if node_level not in max_values or node_number > max_values[node_level]['number']:
            max_values[node_level] = {'name': [node_name], 'number': node_number}
        elif node_number == max_values[node_level]['number']:
            max_values[node_level]['name'].append(node_name)
    
    deepest_level = max(max_values.keys())
    result = max_values[deepest_level]['name']

    return result

原代码的问题在于仅全局按层级找最大值，未区分不同分支。需要先构建树形结构，再针对每个分支单独处理。

def extract_max_values(data):
    # 构建节点映射表，存储节点数据和子节点列表
    node_map = {item['name']: {'data': item, 'children': []} for item in data}
    
    # 遍历数据，为每个节点关联父节点
    for item in data:
        current_level = item['level']
        if current_level == 0:
            continue
        # 找到当前节点的父节点（父节点层级比当前小1，且出现在当前节点之前）
        for prev_item in data[:data.index(item)]:
            if prev_item['level'] == current_level - 1:
                node_map[prev_item['name']]['children'].append(node_map[item['name']])
                break
    
    # 获取根节点的所有子分支（即level1节点对应的独立分支）
    root_branches = node_map['Parent']['children']
    result = []
    
    for branch in root_branches:
        max_level = branch['data']['level']
        deepest_nodes = []
        # 广度优先遍历分支，找出最深层级的所有节点
        queue = [branch]
        while queue:
            current_node = queue.pop(0)
            current_level = current_node['data']['level']
            
            if current_level > max_level:
                max_level = current_level
                deepest_nodes = [current_node]
            elif current_level == max_level:
                deepest_nodes.append(current_node)
            
            queue.extend(current_node['children'])
        
        # 在最深节点中筛选number最大的节点
        if deepest_nodes:
            deepest_nodes.sort(key=lambda x: x['data']['number'], reverse=True)
            result.append(deepest_nodes[0]['data']['name'])
    
    return result

# 测试验证
list_of_dicts = [{'name': 'Parent', 'number': 1299, 'level': 0}, 
{'name': 'A', 'number': 1011, 'level': 1}, 
{'name': 'B', 'number': 789, 'level': 2}, 
{'name': 'C', 'number': 430, 'level': 3},
{'name': 'D', 'number': 300, 'level': 2}, 
{'name': 'E', 'number': -100, 'level': 3},
{'name': 'F', 'number': 74, 'level': 2}, 
{'name': 'G', 'number': 300, 'level': 1}, 
{'name': 'H', 'number': 140, 'level': 2}]

print(extract_max_values(list_of_dicts))  # 输出: ['C', 'H']

代码说明 #

1. 构建节点映射：将每个节点的信息存储在字典中，方便后续查找和关联子节点。
2. 构建树形结构：遍历数据，为每个节点找到对应的父节点，并将当前节点添加到父节点的子节点列表中。
3. 遍历分支找最深节点：对每个独立分支（根节点的子节点）进行广度优先遍历，记录该分支的最深层级及对应节点。
4. 筛选最大值节点：在每个分支的最深层级节点中，找出number值最大的节点名称，加入结果列表。

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