数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中查找二叉树中节点的最大和，且任意两个节点都不相邻
本教程中，我们将讨论一个程序，查找二叉树中节点的最大和，且任意两个节点都不相邻。
为此，我们将提供一棵二叉树。我们的任务是找到具有最大和的子集，且子集中的任何两个节点都不直接相连。
示例
#include <bits/stdc++.h>
using namespace std;
//binary tree node structure
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 sumOfGrandChildren(node* node);
int getMaxSum(node* node);
int getMaxSumUtil(node* node, map<struct node*, int>& mp);
int sumOfGrandChildren(node* node, map<struct node*, int>& mp){
int sum = 0;
if (node->left)
sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
if (node->right)
sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
return sum;
}
//returning maximum sum
int getMaxSumUtil(node* node, map<struct node*, int>& mp) {
if (node == NULL)
return 0;
if (mp.find(node) != mp.end())
return mp[node];
int incl = node->data + sumOfGrandChildren(node, mp);
int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
mp[node] = max(incl, excl);
return mp[node];
}
int getMaxSum(node* node) {
if (node == NULL)
return 0;
map<struct node*, int> mp;
return getMaxSumUtil(node, mp);
}
int main() {
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->left->left = newNode(1);
cout << getMaxSum(root) << endl;
return 0;
}输出
11
更新时间：2020 年 9 月 9 日
165 次浏览
广告