C++ 中不允许计算相邻层级树的最大和
c++server side programmingprogramming
在这个问题中，我们给定一个由正数组成的二叉树。我们的任务是编写一个程序，用于求出 C++ 中不允许相邻层级的树的最大和。
代码说明
在这里，我们将求出树中节点的最大和，且和不包含树中两个相邻层级的节点。
让我们举个例子来理解这个问题:
输出
21
解释
以根节点为起始层级，和 = 5 + 3 + 8 + 1 = 17 以根节点的子节点为起始层级，和 = 2 + 6 + 9 + 4 = 21
解决方法
求最大和的条件之一是没有相邻元素。为此，我们将从根节点(第 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<<"不允许相邻级别的树的最大和是 "<<getMaxSum(root);
return 0;
}
输出
不允许相邻级别的树的最大和是 24
