leetcode_1339. 分裂二叉树的最大乘积
题目链接:1339. 分裂二叉树的最大乘积
DFS两次即可
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MOD ((int)pow(10, 9) + 7)
static void post_order_traversal(struct TreeNode* node)
{
if (!node) {
return;
}
post_order_traversal(node->left);
post_order_traversal(node->right);
if (node->left) {
node->val += node->left->val;
}
if (node->right) {
node->val += node->right->val;
}
}
static void dfs(struct TreeNode* node, const long long sum, long long *ans)
{
if (!node) {
return;
}
long long a = node->val;
long long b = sum - node->val;
*ans = MAX(*ans, (a * b));
dfs(node->left, sum, ans);
dfs(node->right, sum, ans);
}
int maxProduct(struct TreeNode* root){
post_order_traversal(root);
long long sum = root->val;
long long ans = 0;
dfs(root, sum, &ans);
return (ans % MOD);
}