1339. Maximum Product of Splitted Binary Tree¶
题目信息¶
- 题号:
1339
- 难度:
Medium
- 主题:
二叉树、子树和、枚举切边
- 原题:
- 重点:
删除恰好一条边得到两棵子树,最大化两棵树节点值总和的乘积;最终结果对
10^9+7取模
题目重述¶
给定一棵非空二叉树,节点值均为正整数。删除树中的恰好一条边后,会得到两棵非空子树。
计算两棵子树节点值总和的乘积,并返回所有切边方案中的最大乘积对 10^9 + 7 取模后的结果。比较大小时应先使用未取模的乘积。
树中节点数不超过 5 * 10^4,节点值不超过 10^4。
自建示例¶
选择更接近总和一半的子树:
输入:root = [1,2,3]
输出:9
解释:切断根与右孩子的边后,两部分和为 3 和 3,乘积为 9。
两节点树只有一种切法:
输入:root = [5,5]
输出:25
解释:删除唯一边后两棵树的和均为 5。