C++에서 인접하지 않는 이진 트리의 최대 노드 합계

이 튜토리얼에서는 두 노드가 인접하지 않도록 바이너리 트리에서 노드의 최대 합을 찾는 프로그램에 대해 설명합니다.

이를 위해 이진 트리가 제공됩니다. 우리의 임무는 하위 집합의 두 노드가 직접 연결되지 않도록 최대 합을 갖는 하위 집합을 찾는 것입니다.

예

#include <bits/stdc++.h>
using namespace std;
//binary tree node structure
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 sumOfGrandChildren(node* node);
int getMaxSum(node* node);
int getMaxSumUtil(node* node, map<struct node*, int>& mp);
int sumOfGrandChildren(node* node, map<struct node*, int>& mp){
   int sum = 0;
   if (node->left)
      sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
   if (node->right)
      sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
   return sum;
}
//returning maximum sum
int getMaxSumUtil(node* node, map<struct node*, int>& mp) {
   if (node == NULL)
      return 0;
   if (mp.find(node) != mp.end())
      return mp[node];
   int incl = node->data + sumOfGrandChildren(node, mp);
   int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
   mp[node] = max(incl, excl);
   return mp[node];
}
int getMaxSum(node* node) {
   if (node == NULL)
      return 0;
   map<struct node*, int> mp;
   return getMaxSumUtil(node, mp);
}
int main() {
   node* root = newNode(1);
   root->left = newNode(2);
   root->right = newNode(3);
   root->right->left = newNode(4);
   root->right->right = newNode(5);
   root->left->left = newNode(1);
   cout << getMaxSum(root) << endl;
   return 0;
}

출력

11