二叉树中的数和

Question

我有一个列表，可以包含两个自然数或两个以上的列表。每个列表还包含两个整数或两个其他列表，依此类推。e、 i.：[[4,7]，[3,5]，[9,1]]我需要使用递归来计算树中所有数字的总和，并编写以下代码：

def getSum(tree):
    sum = 0
    for elemente in tree:
        if type(elemente)==int:
            sum += elemente
        else:
            sum = getSum(elemente)
    return sum

代码不工作，因为它总是将sum返回到12，所以我的问题是，如何使它工作，但仍然使用递归？。我没有正确地识别基本情况吗？

Answer 1

如果您需要它是递归，您必须将和保持在递归循环之外。

例如：

def getSum(tree, sum = None):
    sum = sum or 0
    for elemente in tree:
        if type(elemente)==int:
            sum += elemente
        else:
            sum = getSum(elemente, sum)
    return sum

tree = [[4, 7], [[3, 5], [9, 1]]]
print(getSum(tree))

29