题目链接:https://leetcode-cn.com/contest/weekly-contest-174/problems/maximum-product-of-splitted-binary-tree/
第一篇LeetCode的题解,今天也是第一次打LeetCode的比赛,这种写题的方式还是不太适应。
这道题的题意还是很好理解,并且给了详细的样例解释,思路不是很难,用了两个dfs,一个用来去遍历一遍二叉树求出这棵树的权值和,第二个dfs就是去枚举每一条边,并更新一个删除这条边之后的代价,这里就不做过多的解释了,代码很容易理解。
AC代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
long long ans;
long long sum;
void dfs1(TreeNode* root){
if(!root) return ;
sum += root->val;
dfs1(root->left);
dfs1(root->right);
}
long long dfs2(TreeNode* root){
if(!root) return 0;
long long x = dfs2(root->left) + dfs2(root->right) + root->val;
ans= max(ans, x * (sum - x));
return x;
}
int maxProduct(TreeNode* root) {
ans = 0;
sum = 0;
dfs1(root);
dfs2(root);
return ans % int(1e9+7);
}
};