C ++中不允许带有相邻级别的树的最大和

在这个问题上，我们得到了一个由正数组成的二叉树。我们的任务是创建一个程序，以从C ++不允许的相邻级别的树中查找最大和。

代码说明

在这里，我们将以这样的方式找到树的最大节点和：该和不包含来自树的两个相邻级别的节点。

让我们举个例子来了解这个问题，

输出结果

21

说明

以root为起始级别，总和= 5 + 3 + 8 +1 = 17以root的子子级为起点，sum = 2 + 6 + 9 + 4 = 21

解决方法

要找到maxSum，一个条件是没有相邻元素。为此，我们将从根节点（级别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