将模拟树的字典转换为列表

Question

我有这样的字典:

{
1: {
   3: {
      1: {c:32},
      2: {c:12}
      },
   4: {c: 66}
   },
2: {
   3: {c: 1},
   5: {c: 2}
   }
}

我怎样才能优雅地展开这棵树来获得:

[
[1, 3, 1, 32],
[1, 3, 2, 12],
[1, 4, 66],
[2, 3, 1],
[2, 5, 2]
]

这种结构可以任意深入.

编辑 - 我不关心输出的顺序.'c'是看到特定整数序列的次数.所以在这种情况下,[1,3,1]被看到32次.

确切的格式并不那么重要,这是我追求的技术.

Answer 1

递归:

def flatten(d, prefix=()):
    for k,v in d.items():
        if isinstance(v, dict):
            yield from flatten(v, prefix=prefix+(k,))
        else:
            yield list(prefix + (v,))

迭代:

from collections import deque

def flatten(d):
    queue = deque([[[], d]])
    while queue:
        prefix, node = queue.popleft()
        if isinstance(node, dict):
            queue.extend([(prefix + [k], v) for k, v in node.items()])
        else:
            yield prefix[:-1] + [node]

注意:在Python中使用递归来压缩堆栈相对容易.如果您的数据很大,即比数据更深sys.getrecursionlimit(),那么您应该更喜欢广度优先的解决方案 - 这可能会占用大量内存,但不会堆叠溢出.