트리 구조 범주는 캐스케이드로 루트 노드로 합입니다
-
12-09-2019 - |
문제
나는 바로 나와서 내가 세상의 위대한 수학자가 아니라고 말할 것입니다. 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 : 지점은 자녀가 누구인지에 대한 언급이 없지만 아이들은 부모가 누구인지 알고 있습니다.
무언가가 불분명하다면 물어 보면 문제를 더 잘 설명하고 설명하겠습니다.
모든 도움이 감사하겠습니다.
해결책
좋아, 레프트는 이것을 찌르지 않는다.
의사 코드로 이렇게 갈 것입니다.
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
다른 팁
트리의 모든 노드의 합을 결정하고 싶습니까?
나무 걷기는 우아한 재귀 솔루션에 적합합니다.
public int SumTree (TreeNode n) {
if(n.isLeafNode) return n.value;
return SumTree(n.left) + SumTree(n.right);
}
이진 트리를 가정합니다.