德州市网站建设_网站建设公司_ASP.NET_seo优化

lc1339

两次递归遍历二叉树

先计算整棵树的节点值总和，再遍历每个子树计算其节点值和

找出子树和与剩余部分和的最大乘积

class Solution {
long long sum = 0, ret = 0;
const int MOD = 1e9 + 7;
public:
int maxProduct(TreeNode* root)
{
cal_sum(root);
dfs(root);
return ret % MOD;
}

void cal_sum(TreeNode* node)
{
if (!node) return;
sum += node->val;
cal_sum(node->left);
cal_sum(node->right);
}

long long dfs(TreeNode* node)
{
if (!node) return 0;
long long sub_sum = dfs(node->left) + dfs(node->right) + node->val;
long long p = sub_sum * (sum - sub_sum);
ret=max(ret,p);
return sub_sum;
}
};