python - 子树中的节点总和(非二叉树)

Question

我当前正在尝试查找指定子树中所有节点的总和。例如，如果我有一棵树

     A(5)
     / \
   B(5) C(6)
   /    /  \
  D(3) E(3) F(7)
            |
            G(1)

我想知道 sum(C)，它应该返回 17。

这是我使用递归想出的代码，但我似乎无法到达具有超过 2 层的子树。例如。我的算法似乎没有达到 G。我试图在递归方面做得更好，但我似乎无法解决这个问题。

def navigate_tree(node,key): #node of the root of subtree, along with its key
    children = node.get_children()
    if (len(children) ==0):
        return node.key
    else:
        for child in children: #not a binary tree so trying to loop through siblings
            key += navigate_tree(child,key) #summing up key recursively
        return key 

Answer 1

改进的界面并能够利用集合的功能会更好:

def navigate_tree(node): 
    children = node.get_children()
    key = node.key
    for child in children:
        key += navigate_tree(child)
    return key

# class Node and data A..G elided
print(navigate_tree(C))

输出:

17

您的代码似乎不起作用的原因是您将前一个键传递到下一个递归级别。但是，您的代码似乎递归正常。如果您添加了一些print(node.key)，您就会发现您正在访问所有正确的节点。