1339. Maximum Product of Splitted Binary Tree

题目信息

题号:

1339

难度:

Medium

主题:

二叉树、子树和、枚举切边

原题:

LeetCode 1339

重点:

删除恰好一条边得到两棵子树,最大化两棵树节点值总和的乘积;最终结果对 10^9+7 取模

题目重述

给定一棵非空二叉树,节点值均为正整数。删除树中的恰好一条边后,会得到两棵非空子树。

计算两棵子树节点值总和的乘积,并返回所有切边方案中的最大乘积对 10^9 + 7 取模后的结果。比较大小时应先使用未取模的乘积。

树中节点数不超过 5 * 10^4,节点值不超过 10^4。

自建示例

选择更接近总和一半的子树:

输入:root = [1,2,3]
输出:9
解释:切断根与右孩子的边后,两部分和为 3 和 3,乘积为 9。

两节点树只有一种切法:

输入:root = [5,5]
输出:25
解释:删除唯一边后两棵树的和均为 5。