从上到下查找通过树(嵌套dicts)的所有路径

Question

编辑:请参阅下面的建议答案,以及它是如何不正确的.

Stack Overflow上有很多类似的问题,但没有一个像Python一样.我是编程新手,所以请放轻松.

我有一个嵌套字典树,如下所示:

[{'word': 'The',
  'next': [{'word': 'End',
            'next': None},
           {'word': 'quick',
            'next': [{'word': 'brown',
                      'next': [{'word': 'fox',
                                'next': None}]}]},
           {'word': 'best',
            'next': [{'word': 'of',
                      'next': [{'word': 'times',
                                'next': None}]}]}]}] 

我想从上到下展平所有路径并最终得到:

[[{'word': 'The'},
  {'word': 'End'}],

 [{'word': 'The'},
  {'word': 'quick'},
  {'word': 'brown'},
  {'word': 'fox'}],

 [{'word': 'The'},
  {'word': 'best'},
  {'word': 'of'},
  {'word': 'times'}]]

我做了一个可爱的小递归函数,它首先创建了原始结构,但我很难将其解除.这是我得到的:

def flatten_combinations(result_tree, current_combo = None, all_combos = None):
    if current_combo is None:
        current_combo = []
    if all_combos is None:
        all_combos = []
    if result_tree is None:
        all_combos.append(current_combo)
        return
    for word in result_tree:
        current_combo.append({'word': word['word']})
        flatten_combinations(word['next'], current_combo, all_combos)
    return current_combo

...返回:

[{'word': 'The'},
 {'word': 'End'},
 {'word': 'quick'},
 {'word': 'brown'},
 {'word': 'fox'},
 {'word': 'best'},
 {'word': 'of'},
 {'word': 'times'}]

......显然有些接近但不太对劲.

我知道这个函数可能非常恐怖,但是我自学编程,所以我甚至都没有试图利用可能存在的语言特性来让我从头开始思考这些东西("他说,发布到Q&A网站,希望其成员会帮助他省略一点思考).

那么:我做错了什么？

编辑:Moshe下面纠正了几个问题:

def flatten_combinations(result_tree, current_combo = None, all_combos = None):
    if current_combo is None:
        current_combo = []
    if all_combos is None:
        all_combos = []
    if result_tree is None:
        all_combos.append(current_combo)
        return
    for word in result_tree:
        current_combo = current_combo[:]
        current_combo.append({'word': word['word']})
        flatten_combinations(word['next'], current_combo, all_combos)
    return all_combos 

这是更接近但不太正确:

[{'word': 'The'}, 
 {'word': 'End'}],

[{'word': 'The'},
 {'word': 'End'},
 {'word': 'quick'},
 {'word': 'brown'},
 {'word': 'fox'}],

[{'word': 'The'},
 {'word': 'End'},
 {'word': 'quick'},
 {'word': 'best'},
 {'word': 'of'},
 {'word': 'times'}]]

Answer 1

其中有两个小错误：

1）你返回current_combo而不是all_combos。这只会给你最后的结果

2) 在每次迭代中，您都会修改current_combo. 先复印一份吧！

new_current_combo = current_combo[:]
new_current_combo.append({'word': word['word']})
flatten_combinations(word['next'], new_current_combo, all_combos)

完整代码：

def flatten_combinations(result_tree, current_combo=None, all_combos=None):
    if current_combo is None:
        current_combo = []
    if all_combos is None:
        all_combos = []
    if result_tree is None:
        all_combos.append(current_combo)
        return
    for word in result_tree:
        new_current_combo = current_combo[:]
        new_current_combo.append({'word': word['word']})
        flatten_combinations(word['next'], new_current_combo, all_combos)
    return all_combos