数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++实现的树中最大和（不允许相邻层）
在这个问题中，我们得到一个由正数组成的二叉树。我们的任务是创建一个程序，用C++查找树中不允许相邻层的最大和。
代码描述
在这里，我们将以这样的方式找到树节点的最大和：和中不包含来自树中两个相邻层的节点。
让我们来看一个例子来理解这个问题：
输出
21
解释
以根节点作为起始层，和 = 5 + 3 + 8 + 1 = 17。以根节点的子节点作为起始层，和 = 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
更新于：2020年10月15日
浏览量 106 次
广告