Pythonの非バイナリツリーの最大合計

Question

私は非バイナリツリーを持ち、そのツリーの各ノードに値があります。私は利用可能な最大合計を取得したいと思います。 例えば：

   10 
     9  8  7 
    1 2 5  5  15 

リターンは10 + 7 + 15 = 32 だろう、私は木がバイナリであればこれを行う方法を知っているが、木はn個の枝を持っている場合はどう？ このコードは、この質問の最初の答えから取られたバイナリ1である：Find the maximum sum of a tree in python

Answer 1

ノード、空のリスト、またはなし：

def tree_sum(node): 
    if node.children: 
     child_sums = [] 
     for child in node.children: 
      child_sums.append(tree_sum(child) + node.value) 
     return max(child_sums) 
    else: 
     return node.value 

print tree_sum(root) 

Answer 2

は、ここに1つのアプローチです：

各ノードは子のリストのいずれかである value属性と children属性を持っていると仮定すると、

class Node: 
    def __init__(self, value): 
     self.value = value 
     self.children = [] 


def max_sum(root): 
    if len(root.children) == 0: 
     return root.value 

    sums = [] 
    for child in root.children: 
     sums.append(root.value + max_sum(child)) 

    return max(sums) 


n_9 = Node(9) 
n_9.children.extend([Node(1), Node(2), Node(5)]) 

n_8 = Node(8) 
n_8.children.extend([Node(5)]) 

n_7 = Node(7) 
n_7.children.extend([Node(15)]) 

n_10 = Node(10) 
n_10.children = [n_9, n_8, n_7] 

print max_sum(n_10) 
# Output: 32