python - 每个深度的二叉树遍历总和

Question

我正在寻找一种算法或修改一种有效的方法来获取树深度的遍历总和，例如:

                Z
               / \
              /   \
             /     \
            /       \
           X         Y
          / \      /  \
         /   \    /    \
        A     B  C      D

最终叶子的数量是四，所以我们有四个最终总和，它们分别是这样。

[Z+X+A] [Z+X+B] [Z+Y+C] [Z+Y+D]

如果有人能指导我在正确的方向上获得所有可能深度的总和，那就太好了。

这将在具有相当大的树的 python 中完成。

Answer 1

您可以递归树的节点，保持从根到这一点的总和。当您到达叶节点时，您将返回一个元素列表中的当前总和。在内部节点中，您连接从子节点返回的列表。

示例代码:

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

def tree_sums(root, current_sum):
    current_sum += root.value
    if len(root.children) == 0:
        return [current_sum]
    subtree_sums = []
    for child in root.children:
        subtree_sums += tree_sums(child, current_sum)
    return subtree_sums

tree = Node(1, [Node(2, []), Node(3, [])])
assert tree_sums(tree, 0) == [3, 4]