编写一个函数，接受一棵树和 returns 树中任何路径上的值的最大总和

Question

我正在看这个编码问题：

Write a function that takes in a tree and returns the maximum sum of the values along any path in the tree. Recall that a path is from the tree's root to any leaf.

随附以下样板代码：

def tree(root_label, branches=[]):
    for branch in branches:
        assert is_tree(branch)
    return [root_label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

def max_path_sum(t):
    """Return the maximum path sum of the tree.

    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t)
    11
    """
    "*** YOUR CODE HERE ***"

如何使用这些预定义函数递归定义 max_path_sum 函数？

Answer 1

对分支递归调用该函数，并将当前节点的标签添加到这些子结果的最大值：

def max_path_sum(t):
    return label(t) + max(map(max_path_sum, branches(t)), default=0)

默认参数涵盖 t 是叶子的情况，在这种情况下，结果将只是节点的标签。

你也可以调用is_leaf来区分，但是这样会使代码变长：

def max_path_sum(t):
    if is_leaf(t):
        return label(t)
    return label(t) + max(map(max_path_sum, branches(t)))

编写一个函数，接受一棵树和 returns 树中任何路径上的值的最大总和

Write a function that takes in a tree and returns the maximum sum of the values along any path in the tree

python

tree

binary-tree