python - 枚举树中的所有路径并操作与每个节点关联的值

Question

灵感来自 answer到 question "Enumerating all paths in a tree" ，我写了一个改编版本(我不需要无根路径):

def paths(tree):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        rooted_paths = [[root]]
        for subtree in tree.nextDest:
            useable = paths(subtree)
            for path in useable:
                rooted_paths.append([root]+path)
    return rooted_paths

现在，在我的“树”对象中，我有一个与每个节点关联的数字:tree.number。我看起来像这样:

     A,2
    /   \
  B,5   C,4
   |    /  \
  D,1  E,4 F,3

我想用 0 值初始化我的路径，并对路径的所有 tree.numbers 求和，以便知道每个生成路径的总和:

A-B-D: 8
A-C-E: 10
A-C-F: 9

我应该如何修改我的代码才能得到这个结果？我不知道该怎么做。

Answer 1

为了实现您想要的结果，将另一个参数传递给递归 - 这将是您目前获得的总和。还为每条路径再返回一个值 - 它的总和:

def paths(tree, sum_so_far):
    #Helper function
    #receives a tree and 
    #returns all paths that have this node as root
    if not tree:
        return []
    else: #tree is a node
        root = tree.ID
        val = tree.Value
        rooted_paths = [[[root], value]]
        for subtree in tree.nextDest:
            useable = paths(subtree, sum_so_far + val)
            for path in useable:
                rooted_paths.append([[root]+path[0], path[1]])
    return rooted_paths

像这样的东西应该可以工作。请注意，现在您返回的是一对路径和整数值的数组。整数值是沿该路径的总和。

希望对您有所帮助。