Python 中非二叉树的最大总和

Question

我有一棵非二叉树，该树的每个节点都有一个值。我想获得最大可用金额。例如：

              10
       9       8      7
    1  2  5     5      15

return就是10+7+15=32 如果树是二叉树，我知道该怎么做，但是如果树有 n 个分支怎么办？此代码是从该问题的第一个答案中获取的二进制代码：Find the maximum sum of a tree in python

Answer 1

这是一种方法：

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

Answer 2

假设每个节点都有一个 value 属性和一个 children 属性，它可以是子节点列表、空列表或 None:

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)

Python 中非二叉树的最大总和

Maximum sum in a non-binary tree in Python

python

tree

recursion