隣接するレベルを持つツリーからの最大合計はC++では許可されていません

この問題では、正の数で構成される二分木が与えられます。私たちのタスクは、C++では許可されていない隣接するレベルを持つツリーから最大合計を見つけるプログラムを作成することです。

コードの説明

ここでは、ツリーの2つの隣接するレベルのノードが合計に含まれないように、ツリーのノードの最大合計を求めます。

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

出力

21

説明

ルートを開始レベルとして、合計=5 + 3 + 8 + 1 =17ルートのサブ子を開始レベルとして、合計=2 + 6 + 9 + 4 =21

ソリューションアプローチ

maxSumを見つけるための条件のひとつは、隣接する要素がないことです。このために、ルートノード（レベル1）から1つの合計セットを取得し、子ノード（レベル2）から別の合計セットを取得します。次の合計ノードは、孫ノードを見つけることによって現在のノードから抽出されます。

このために、maxSum値を再帰的に見つけ、レベル1またはレベル2から始まる合計の最大合計値が結果のmaxSumになります。

例

ソリューションの動作を説明するプログラム

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node* left, *right;
   Node(int item){
      data = item;
   }
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
   if (root == NULL)
      return 0;
      int sum = root->data;
   if (root->left != NULL){
      sum += getMaxSum(root->left->left);
      sum += getMaxSum(root->left->right);
   }
   if (root->right != NULL){
      sum += getMaxSum(root->right->left);
      sum += getMaxSum(root->right->right);
   }
   return sum;
}
int getMaxSum(Node* root){
   if (root == NULL)
      return 0;
      return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
   Node* root = new Node(5);
   root->left = new Node(2);
   root->right = new Node(10);
   root->left->left = new Node(4);
   root->left->right = new Node(6);
   root->right->right = new Node(9);
   cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
   return 0;
}

出力

The maximum sum from a tree with adjacent levels not allowed is 24