1339. 分裂二叉树的最大乘积

 

链接：

​​​​​​1339. 分裂二叉树的最大乘积

题解：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxProduct(TreeNode* root) {if (!root) {return 0;}int sum = 0;dfs(root, sum);long long result = 0;dfs2(root, sum, result);        int mod = 1000000007;return result%mod;}
private:void dfs(TreeNode* root, int& sum) {if (!root) {return;}sum += root->val;dfs(root->left, sum);dfs(root->right, sum);}int dfs2(TreeNode* root, int sum, long long& result) {if (!root) {return 0;}long long cur = dfs2(root->left, sum, result) + dfs2(root->right, sum, result) + root->val;long long tmp_result = (sum-cur)*cur;if (tmp_result > result) {result = tmp_result;}return cur;}
};