如何编写对树中的整数求和的递归函数？

Question

写一个递归函数TreeSum(T) 把树中的所有整数相加。我的测试用例是

TreeSum(set)

48

哪里

set=[[[[2,1],[3,7]],[1,2]],[[0,6],[[[3,2],[1,1]],[9,10]]]]

这是我目前的代码：

def TreeSum(T):
     if len(T)==0:
       return 0
     else:
       return T[0] + TreeSum(T[1:])

我从 return 行收到错误消息（“只能将列表（而不是“int”）连接到列表”）。我怎样才能解决这个问题？错误：

----> 5    return T[0] + TreeSum(T[1:])
      6 
      7 TreeSum(maple)

TypeError: can only concatenate list (not "int") to list

Answer 1

@j1-lee 有正确的方法，但这在子列表的跨度方面是有限的（默默地忽略位置 > 1 的项目，或者如果前两个元素之一是整数则失败）。您需要对所有 sub-elements 应用递归函数。一种方法是使用 map

注意。我稍微更改了输入以将两个元素添加到第一个子列表

tree = [[[[2,1],1,[3,7],[1]],[1,2]],[[0,6],[[[3,2],[1,1]],[9,10]]]]

def treesum(x):
    if not isinstance(x, list):
        return x
    return sum(map(treesum, x))
print(treesum(tree))

输出：50

如何编写对树中的整数求和的递归函数？

how to write a recursive function that sums the integers in a tree?

python

tree

recursion

binary-tree