树结构类别总和即级联到根节点

Question

我要直截了当地说，我不是世界上最伟大的数学家：D所以这个问题很可能是简单，你们中的大多数。不幸的是它的困惑我和曾在可行的解决方案的几个刺。

与任何树，可以有许多分支，许多分支可以有更多的分支，并依此类推，直到它们与叶节点结束。我有在每个指示它的值叶信息。

我需要的是如何解决总结每个叶节点值作为一个整体它的问题明确explination的分支机构（父）和做同样的休息，但不要忘记，如果一个分支是由其他部门共享它是每个下水平分支和叶，其直接关系到本身的概要信息。

为了更好地解释：

Root
|----Branch
|         |-Leaf 10
|----Branch
|         |----Branch
|         |-Leaf 20 |-Leaf 30
|----Branch         |-Leaf 40
|         |----Branch
|                   |----Branch
|                             |----Leaf 50
|-Leaf 60

的目标是：

Root 210
|----Branch 10
|         |-Leaf 10
|----Branch 90
|         |----Branch 70
|         |-Leaf 20 |-Leaf 30
|----Branch 50      |-Leaf 40
|         |----Branch 50
|                   |----Branch 50
|                             |----Leaf 50
|-Leaf 60

我能够识别的最低水平部件（叶节点），根节点和分支本身。我没有在树枝上是否有其他分支链接到自己低了下去，或直接连接到叶节点标识。的关系是非常底向上根。 IE：分支没有提及是谁的孩子，但孩子知道父母是谁。

请，如果事情不清楚问我会试着更好地解释这个问题。

任何帮助，将不胜感激。

Answer 1

行，这左派得到刺

我会去像这样一些伪代码

foreach leaf in knownLeafs
    parent = leaf.parent //get the leaf parent
    parent.total = parent.total + leaf.value //add leaf value to parent total
    while parent.parent != null //loop until no more parents, this would be the root
    {
        current = parent
        parent = parent.parent //move up the structure
        parent.total = parent.total + current.total
    }
next leaf

您需要创建将，给定一个节点的功能，返回父节点

节点GetParentNodeFrom（节点）

新的伪代码看起来像这样

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent

parent.total = parent.total + leaf.value //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + current.total
}
next leaf

对不起，我的错，你应该只移动门扇价值高达，不是太总数。 看到用于新leafValue。

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent
leafValue = leaf.value
parent.total = parent.total + leafValue //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + leafValue
}
next leaf

Answer 2

您要确定树中的所有节点的总和？

树行走使其本身和优雅的递归溶液：

public int SumTree (TreeNode n) {
    if(n.isLeafNode) return n.value;
    return SumTree(n.left) + SumTree(n.right);
}

假设一个二叉树。