数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 程序中的动态规划查找二叉树中节点的最大和，且这些节点互不相邻
在这个问题中，我们给定一个二叉树，每个节点都有一个值。我们的任务是创建一个程序，使用动态规划查找二叉树中节点的最大和，且这些节点互不相邻。
问题描述 − 我们将选择二叉树的子集，使和最大化，并且这些节点不能直接连接。
让我们举个例子来理解这个问题，
输入
输出
24
解释
Elements to be taken under consideration are: 8 + 5 + 9 + 2 = 24
解决方案方法
解决此问题的方法是使用映射并找到节点的总和，使得它们形成 maxSum。根据给定的条件，节点及其子节点都不能
考虑在总和中。因此，我们需要在考虑节点之前检查其子树是否包含构成更大总和的某些元素。
对于每个节点，多次查找相同父-子子树的总和会增加计算开销，为了解决这个问题，我们将使用记忆化并将节点的 maxSum 存储在映射中，以便以后使用。
示例
程序说明了我们解决方案的工作原理，
#include <bits/stdc++.h>
using namespace std;
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 findMaxSumBT(node* node, map<struct node*, int>& nodeSum);
int sumSubTreeNodes(node* node, map<struct node*, int>& nodeSum){
int maxSum = 0;
if (node−>left)
maxSum += findMaxSumBT(node−>left−>left, nodeSum) +
findMaxSumBT(node−>left−>right, nodeSum);
if (node−>right)
maxSum += findMaxSumBT(node−>right−>left, nodeSum) +
findMaxSumBT(node−>right−>right, nodeSum);
return maxSum;
}
int findMaxSumBT(node* node, map<struct node*, int>& nodeSum){
if (node == NULL)
return 0;
if (nodeSum.find(node) != nodeSum.end())
return nodeSum[node];
int sumInclCurr = node−>data + sumSubTreeNodes(node, nodeSum);
int sumExclCurr = findMaxSumBT(node−>left, nodeSum) +
findMaxSumBT(node−>right, nodeSum);
nodeSum[node] = max(sumInclCurr, sumExclCurr);
return nodeSum[node];
}
int main(){
node* root = newNode(9);
root−>left = newNode(4);
root−>right = newNode(7);
root−>left−>left = newNode(8);
root−>left−>right = newNode(5);
root−>right−>left = newNode(2);
map<struct node*, int> nodeSum;
cout<<"Maximum sum of nodes in Binary tree such that no two are
adjacent using Dynamic Programming is "<<findMaxSumBT(root,
nodeSum);
return 0;
}输出
Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is 24
更新于: 2020-12-09
382 次查看
广告