企业官网建设流程全解析

怎麽用dw做网站轮播海报,网站开发实训的心得,杭州专业网站营销,企业制度型开放论坛给你一棵二叉树#xff0c;它的根为 root 。请你删除 1 条边#xff0c;使二叉树分裂成两棵子树#xff0c;且它们子树和的乘积尽可能大。由于答案可能会很大#xff0c;请你将结果对 10^9 7 取模后再返回。示例 1#xff1a;输入#xff1a;root [1,2,3,4,5,6] 输出它的根为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(pNULL)return; Free(p-left); Free(p-right); free(p); } node *build_tree(struct TreeNode *r) { if(rNULL)return NULL; node *p(node*)malloc(sizeof(node)); p-valr-val*1LL; p-leftbuild_tree(r-left);p-rightbuild_tree(r-right); if(p-left!NULL)p-left_sump-left-valp-left-left_sump-left-right_sum; else p-left_sum0; if(p-right!NULL)p-right_sump-right-valp-right-left_sump-right-right_sum; else p-right_sum0; return p; } long long get_ans(node *p,long long total) { if(pNULL)return 0; long long sum0,sum_lp-left_sum,sum_rp-right_sum; if(sum_l*2total)sum_ltotal-sum_l; if(sum_r*2total)sum_rtotal-sum_r; sumfmax(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 mod1e97,sum0,ans0,total0; node *rbuild_tree(root);totalr-valr-left_sumr-right_sum; ansget_ans(r,total); Free(r); return ans*(total-ans)%mod; }