寻找树的最大高度并返回该路径的总和

Question

   1
 2   3
        returns 1 + 3 = 4

我想先找出一棵树的最大高度，然后再计算它所有节点的总和。

如果有两条路径的高度相同，那么只会返回那条总和更大的路径。

抱歉我的例子不太好……我想表达的是，上面这样的树

应该有像 [1, [2, None, None], [3, None, None]] 这样的树形列表，而不是 [1,2,3]。

Answer 1

这些值是权重吗？树的结构有排序吗（树的节点有特定的顺序吗）？

如果是这样的话，也许你可以尝试一种修改版的迪杰斯特拉算法，在每个交叉点选择最长的距离，而不是最短的。同时，使用一个栈而不是最小优先队列，这样你就可以进行深度优先遍历，而不是广度优先遍历。

编辑：

我再想想，也许使用最大优先队列会更好。我还是不太明白你想要实现什么。我觉得你可能是在寻找总和最大的路径，但这并不一定意味着它会是节点最多的那条路径。因为每个节点似乎都有权重，所以节点最多的路径可能没有意义，因为可能存在更短但权重更大的路径。

Answer 2

def tree_height(tree):
    if (isinstance(tree, list)):
        tree = tree[1:]
        if (tree):
            return (1 + max([tree_height(x) for x in tree]))
    return 0

def tree_sum(tree):
    if tree and (isinstance(tree, list)):
        return tree[0] + sum([tree_sum(x) for x in tree[1:]])
    return (tree or 0)

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 3

这是Egg推荐的递归函数：

def sum_of_longest_branch(tree):
    """
    Parses a tree and returns a tuple containing (depth, sum) of deepest branch.
    """
    # stop conditions on leave nodes (can be single [node] or None)
    if 1 == len(tree):
        return 1, tree[0]
    elif None == tree:
        return 1, 0
    # splitting the branches
    else:
        # calling the function recursively on all branches branching from current node
        branches_sums = [sum_of_longest_branch(branch) for branch in tree[1:]]
        # extracting the currently deepest branch
        branch, sum = sorted(branches_sums, reverse=True)[0]
        # add own node value and one depth before returning
        return branch + 1, sum + tree[0]

示例：

tree = [1, [2, [4]], [3, [0]]]
depth, sum = sum_of_longest_branch(tree)
print depth, sum

结果是：

3, 7 

抱歉如果这个代码看起来有点粗糙，但它确实能工作。这个问题其实并不简单，特别是对于刚开始学习编程或Python的人。我希望你能理解。

编辑：现在首先检查深度，然后再检查总和。