数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找树中最大的子树和
在这个问题中，我们给定一棵二叉树。我们的任务是找到树中最大的子树和。
问题描述：二叉树包含正值和负值。我们需要找到节点和最大的子树。
让我们举个例子来理解这个问题，
输出：13
解释：
左子树的和为 7
右子树的和为 1
树的和为 13
解决方案方法
为了解决这个问题，我们将进行后序遍历。计算左子树和右子树的节点和。对于当前节点，检查当前节点的节点和是否大于左子树或右子树的和。对于每个节点，从叶子到根找到最大和。
程序说明我们解决方案的工作原理，
示例
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
Node* newNode(int key) {
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
int calcSumTreeSumRec(Node* root, int& ans) {
if (root == NULL)
return 0;
int currSum = root->key + calcSumTreeSumRec(root->left, ans)+ calcSumTreeSumRec(root->right, ans);
ans = max(ans, currSum);
return currSum;
}
int calcMaxSubTreeSum(Node* root)
{
if (root == NULL)
return 0;
int ans = -100;
calcSumTreeSumRec(root, ans);
return ans;
}
int main() {
Node* root = newNode(5);
root->left = newNode(-4);
root->right = newNode(4);
root->left->left = newNode(3);
root->left->right = newNode(8);
root->right->left = newNode(-5);
root->right->right = newNode(2);
cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
return 0;
}输出
The largest subtree sum is 13
更新于：2021-01-25
311 次查看
广告