C++の動的計画法を用いて二分木内の互いに隣接しないノードの最大合計を求める方法

この問題では、各ノードに値が設定された二分木が与えられます。動的計画法（DP）を活用し、選択したノード同士が互いに隣接しないという条件下で、二分木のノード値の合計として考えられる最大値を求めるプログラムを作成することが課題です。

問題の詳細

二分木の中からノードの部分集合を選び、合計値を最大化します。ただし、選んだノード同士が直接的な親子関係でつながっていてはなりません。つまり、あるノードを選んだ場合、その親ノードおよび子ノードは選択できないという制約があります。

入力例

出力例

24

解説

この例では、合計に含めるノードは以下のとおりです。

8 + 5 + 9 + 2 = 24

解法のアプローチ

この問題は、マップ（連想配列）を活用しながら、最大合計（maxSum）を構成するノードの和を求めることで解決できます。制約条件により、あるノードとその子ノードを同時に合計へ含めることはできません。そのため、あるノードを合計に加えるかどうかを判断する前に、その子の部分木により大きな合計を形成する要素が存在しないかを確認する必要があります。

また、各ノードについて同じ親子部分木の合計を何度も再計算すると、計算コストが増大してしまいます。そこでメモ化を利用し、各ノードまでの最大合計をマップに保存しておくことで、一度計算した結果を後から再利用できるようにします。

実装例

以下は、本解法の動作を示すC++プログラムです。

#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