遞歸函數返回字典

Question

我有一個二叉搜索樹，其中每個節點代表遊戲的長度。我必須返回一個字典，其中密鑰是遊戲的長度，值是具有該長度的遊戲的數量。遞歸調用遍歷樹中的每個節點，但它返回不正確的字典。我認爲問題在於我如何返回字典。任何幫助將不勝感激

game_len = {} 
if not node.children: 
    key = len(node.possible_next_moves()) 
    if key not in game_len: 
     game_len[key] = 1 
    else: 
     game_len[key] += 1 
else: 
    key = len(node.possible_next_moves()) 
    if key not in game_len: 
     game_len[key] = 1 
    else: 
     game_len[key] += 1 
    [game_lengths(child) for child in node.children] 
return game_len 

Answer 1

一般來說，有兩種方法來處理來自遞歸算法的返回值。您可以從遞歸調用中收集返回值併合並它們，或者您可以傳遞遞歸調用可以修改的額外的可變參數。我認爲後者在這種情況下可能是最好的，因爲字典很容易變異，但不是特別容易合併在一起：

def game_lengths(node, result=None): 
    if result is None: 
     result = {} 

    #... add a value to the result dict, handle base cases, etc. 

    for child in node.children: 
     game_lengths(child, result) 

    return result