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

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

Recursion:

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() 更深，那么您应该更喜欢宽度优先的解决方案 - 这可能会消耗大量内存，但不会 stack overflow .