트리 구조 범주는 캐스케이드로 루트 노드로 합입니다

Question

나는 바로 나와서 내가 세상의 위대한 수학자가 아니라고 말할 것입니다. D이 문제는 대부분의 사람들에게 간단 할 수 있습니다. 불행히도 그것은 나를 혼란스럽게하고 있으며 실행 가능한 솔루션에서 몇 가지 찌르기를했습니다.

다른 나무와 마찬가지로, 많은 분기를 가질 수 있으며, 많은 지점에 더 많은 가지가 잎 노드로 끝날 때까지 더 많은 가지 등을 가질 수 있습니다. 나는 그 가치를 나타내는 각 잎에 대한 정보가 있습니다.

내가 요구하는 것은 각 잎 노드 값을 분기 (부모)에 대해 총으로 요약하는 문제를 해결하고 나머지는 동일하지만 다른 지점에서 분기가 공유되는 경우를 잊지 않는 방법에 대한 명확한 설명입니다. 그 자체와 직접 관련된 각 하위 레벨 분기 및 잎의 요약.

더 잘 설명하려면 :

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

죄송합니다, 내 실수, 당신은 총계가 아니라 잎 값 만 움직여야합니다. 사용 된 새로운 잎 값을 참조하십시오.

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);
}

이진 트리를 가정합니다.