C++プログラムの動的計画法を使用して2つが隣接しないようなバイナリツリーのノードの最大合計

この問題では、各ノードに値を持つバイナリツリーが与えられます。私たちのタスクは、2つが隣接しないようにバイナリツリー内のノードの最大合計を見つけるプログラムを作成することです。動的計画法を使用します。

問題の説明 −ノードが直接接続されないように合計が最大になるように、バイナリツリーのサブセットを選択します。

問題を理解するために例を見てみましょう

入力

出力

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