在 C++ 中查找树中的最大子树和
c++server side programmingprogramming
在这个问题中，我们给出了一棵二叉树。我们的任务是查找树中的最大子树和。
问题描述：二叉树由正值和负值组成。我们需要找到节点总数最大的子树。
我们举个例子来理解这个问题，
输出：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<<"最大子树和为"<<calcMaxSubTreeSum(root);
return 0;
}
输出
最大子树和为 13
