이 문제에서는 각 노드에 값이 있는 Binary Tree가 제공됩니다. 우리의 임무는 두 노드가 인접하지 않도록 Binarytree에서 노드의 최대 합을 찾는 프로그램을 만드는 것입니다. 동적 프로그래밍을 사용합니다.
문제 설명 − 노드가 직접 연결되지 않는 방식으로 합을 최대화하기 위해 이진 트리의 하위 집합을 선택합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
출력
24
설명
Elements to be taken under consideration are: 8 + 5 + 9 + 2 = 24
해결 방법
문제에 대한 해결책은 맵을 사용하고 노드가 maxSum을 형성하는 노드의 합을 찾는 것입니다. 노드와 해당 자식 모두
주어진 조건에 따라 합계를 고려합니다. 따라서 노드를 고려하기 전에 자식 트리에 더 큰 합계를 구성하는 요소가 있는지 확인해야 한다는 사실을 확인해야 합니다.
각 노드에 대해 동일한 부모-자식 하위 트리의 합을 여러 번 찾는 것은 계산 오버헤드를 증가시키고 이를 처리하기 위해 암기를 사용하고 나중에 사용할 수 있는 맵의 노드까지 maxSum을 저장합니다.
예
우리 솔루션의 작동을 설명하는 프로그램
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
struct node *left, *right;
};
struct node* newNode(int data){
struct node *temp = new struct node;
temp−>data = data;
temp−>left = temp−>right = NULL;
return temp;
}
int findMaxSumBT(node* node, map<struct node*, int>& nodeSum);
int sumSubTreeNodes(node* node, map<struct node*, int>& nodeSum){
int maxSum = 0;
if (node−>left)
maxSum += findMaxSumBT(node−>left−>left, nodeSum) +
findMaxSumBT(node−>left−>right, nodeSum);
if (node−>right)
maxSum += findMaxSumBT(node−>right−>left, nodeSum) +
findMaxSumBT(node−>right−>right, nodeSum);
return maxSum;
}
int findMaxSumBT(node* node, map<struct node*, int>& nodeSum){
if (node == NULL)
return 0;
if (nodeSum.find(node) != nodeSum.end())
return nodeSum[node];
int sumInclCurr = node−>data + sumSubTreeNodes(node, nodeSum);
int sumExclCurr = findMaxSumBT(node−>left, nodeSum) +
findMaxSumBT(node−>right, nodeSum);
nodeSum[node] = max(sumInclCurr, sumExclCurr);
return nodeSum[node];
}
int main(){
node* root = newNode(9);
root−>left = newNode(4);
root−>right = newNode(7);
root−>left−>left = newNode(8);
root−>left−>right = newNode(5);
root−>right−>left = newNode(2);
map<struct node*, int> nodeSum;
cout<<"Maximum sum of nodes in Binary tree such that no two are
adjacent using Dynamic Programming is "<<findMaxSumBT(root,
nodeSum);
return 0;
} 출력
Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is 24