给你一棵二叉树，它的根为root。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
示例 1：
输入：root = [1,2,3,4,5,6]输出：110解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）
示例 2：
输入：root = [1,null,2,3,4,null,null,5,6]输出：90解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）
示例 3：
输入：root = [2,3,9,10,7,8,6,5,4,11,1]输出：1025
示例 4：
输入：root = [1,1]输出：1
提示：
- 每棵树最多有
50000个节点，且至少有2个节点。 - 每个节点的值在
[1, 10000]之间。
分析：当两个数的和为定值时，若想乘积最大，则两个数的差应当尽可能小。可以先 DFS 求出所有节点的和，再进行一次 DFS，对每个节点求出它的左子树和与右子树和，再分别检查这两个和与总结点和一半的距离，保留所有节点距离总和一般最近的值，最后求乘积即可。即 DFS 过程中先不计算乘积，最后只计算一次乘积。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ typedef struct node { struct node *left,*right; long long val,left_sum,right_sum; }node; void Free(node *p) { if(p==NULL)return; Free(p->left); Free(p->right); free(p); } node *build_tree(struct TreeNode *r) { if(r==NULL)return NULL; node *p=(node*)malloc(sizeof(node)); p->val=r->val*1LL; p->left=build_tree(r->left);p->right=build_tree(r->right); if(p->left!=NULL)p->left_sum=p->left->val+p->left->left_sum+p->left->right_sum; else p->left_sum=0; if(p->right!=NULL)p->right_sum=p->right->val+p->right->left_sum+p->right->right_sum; else p->right_sum=0; return p; } long long get_ans(node *p,long long total) { if(p==NULL)return 0; long long sum=0,sum_l=p->left_sum,sum_r=p->right_sum; if(sum_l*2>total)sum_l=total-sum_l; if(sum_r*2>total)sum_r=total-sum_r; sum=fmax(sum_l,sum_r); return fmax(sum,fmax(get_ans(p->left,total),get_ans(p->right,total))); } int maxProduct(struct TreeNode* root) { long long mod=1e9+7,sum=0,ans=0,total=0; node *r=build_tree(root);total=r->val+r->left_sum+r->right_sum; ans=get_ans(r,total); Free(r); return ans*(total-ans)%mod; }
