二叉树的遍历和每一深度 [英] Binary Tree Traversal Sum Of Each Depth

问题描述

我要寻找的有效方法的算法或修改以获得运行的和通过树的深度，例如：

I am looking for an algorithm or modification of an efficient way to get the sum of run through of a tree depth, for example:

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

最终叶片的数目是四个，我们有四个最终总和并且分别他们将是这样。

The number of final leaves is four so us have four final sums and they would be this respectively.

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

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

如果有人可以指导我在正确的方向进获得所有可能的深度的总和，这将是巨大的。

If someone could guide me in the right direction into getting the sums of all possible depths, that would be great.

这将在蟒蛇有相当大的树木做了。

This will be done in python with fairly large trees.

推荐答案

您可以通过递归树保持从根本上总结下来到这一点的节点。当你到达一个叶子结点，返回当前的总和在一个元素的列表。在内部节点，您连接儿童返回的列表中。

You can recurse over the nodes of the tree keeping the sum from the root down to this point. When you reach a leaf node, you return the current sum in a list of one element. In the internal nodes, you concatenate the lists returned from children.

样品code：

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]

这篇关于二叉树的遍历和每一深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！