在树中找到最长（最深）链并求和节点吗？

Question

这里有一些我写的代码，可以用来计算树的深度。

if isinstance(t, list):
        return 1 + max(depth(item) for item in t)
    else:
        return 0

这棵树的结构是这样的：

element 1 is an integer
element 2 is another treelist or None
element 3 is another treelist or None

ex: [1,[1,None,None],None]

example: tree = [12, [1, None, None], [3, [4, None, None], [2, None, None]]]

我的目标是计算到达最深节点的所有节点的总和。如果有多个节点的深度相同，我只想要最大的总和。我可以写一个函数来计算所有节点的总和，但我不知道怎么只计算到达最深节点的那条特定路径……我一直在思考这个问题，但找不到解决办法。

我想到了一种方法，就是通过一个包含左右节点的列表来跟踪这条路径。所以它会是：

[left,right,left]

然后我会用这个来计算总和：

t[0] + t[1] + t[1][0]+ t[1][0][2] . . . and so on, but that seems overly complicated..

有什么想法吗？

编辑： 我又想到了另一种方法： 把所有可能的路径组合存储为列表，放在一个大列表里，然后用我写的深度函数只比较相同长度（深度）的列表，最后取这些列表中最大的总和。不过我还是遇到了同样的问题，我不知道怎么提取单独的路径。而且这样似乎也不太高效。

Answer 1

同样的意思，但更详细一些；可能更容易理解...

tree = [12, [1, None, None], [3, [4, None, None], [2, None, None]]]

mx=0
depth=0

def walk(t,m=0,l=0):
    global mx, depth
    l += 1
    m += t[0]
    for b in t[1:]:
        if b:
            walk(b,m,l)
        else:
            print "level",l,"maximum",m
            if m > mx:
                mx = m
            if l > depth:
                depth = l


walk(tree)
print depth,mx

Answer 2

最简单的解决办法是用递归的方法。也就是说，在树的每一个节点上，答案就是当前节点的值加上左边或右边子节点的值，具体取决于哪个子节点更深（如果它们的最大深度相同，就看哪个子节点的总值更大）。

VALUE, LEFT, RIGHT = 0, 1, 2

def get_deepest_max_sum(node):
    if node is None:
        return 0, 0
    else:
        deepest, most = max(get_deepest_max_sum(node[LEFT]), get_deepest_max_sum(node[RIGHT]))
        return 1+deepest, node[VALUE]+most

tree = [12, [1, None, None], [3, [4, None, None], [2, None, None]]]
print(get_deepest_max_sum(tree))

这样就得到了

(3, 19)   # => depth 3, sum 19