迭代地将任意深度列表转换为字典

Question

输入有一个模式，列表中的每个元素都是一个字典并且有固定的键

[{'key': 'a', 'children': [{'key': 'a1', 'children': [{'key': 'a11', 'children': []}]}]}, {'key': 'b', 'children': [{'key': 'b1', 'children': [{'key': 'b11', 'children': []}]}]},]

预期产出

{'a': {'a1': {'a11': ''}}, 'b': {'b1': {'b11': ''}}}

我想以迭代的方式做到这一点，目前我能够获取固定键的所有值

key

，但无法组合到目标字典

def get_res(stack, key='key'):
    result = []
    while stack:
        elem = stack.pop()
        if isinstance(elem, dict):
            for k, v in elem.items():
                if k == key:
                    # breakpoint()
                    result.append(v)
                stack.append(v)
        elif isinstance(elem, list):
            stack.extend(elem)
    print(result)
    return result

也陷入了递归方法

def gen_x(stack):
    for bx in stack:
        if 'children' not in bx:
            return {bx['key']: ''}
        tem_ls = bx['children']
        xs = gen_x(tem_ls)
        print(xs)

Answer 1

递归方法是这里的自然选择。您可以在递归函数中使用 dict 理解：

def to_dict(lst):
    if not lst:
        return ""
    return { obj["key"]: to_dict(obj["children"]) for obj in lst }

这样称呼它：

lst = [{'key': 'a', 'children': [{'key': 'a1', 'children': [{'key': 'a11', 'children': []}]}]}, {'key': 'b', 'children': [{'key': 'b1', 'children': [{'key': 'b11', 'children': []}]}]},]

result = to_dict(lst)

遗憾的是，您希望“叶子”节点有一个空字符串作为值，这偏离了其他值始终是字典的事实。我会分配空字典，这看起来更一致，然后函数的代码将只包含理解表达式：

def to_dict(lst):
    return { obj["key"]: to_dict(obj["children"]) for obj in lst }

Answer 2

您可以使用队列执行广度优先搜索：

from collections import deque
from operator import itemgetter

def convert_tree(lst):
    tree = {}
    queue = deque([(lst, tree)])
    while queue:
        entries, branch = queue.popleft()
        for key, children in map(itemgetter('key', 'children'), entries):
            if children:
                queue.append((children, branch.setdefault(key, {})))
            else:
                branch[key] = ''
    return tree

演示：https://ideone.com/hvfqLj