LeetCode 1339. Maximum Product of Splitted Binary Tree

用户头像
隔壁小王
关注
发布于: 2020 年 06 月 05 日

Description

Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.



Since the answer may be too large, return it modulo 10^9 + 7.

Example

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)



图片来源:LeetCode



题意分析

  1. 根据题意,首先需要求得树中每个节点及其所在子树的节点和;

  2. 去除某个辺,等同于:去除某个节点,及其子树。因此需要遍历二叉树,找到最优解即可。

对于节点node,最优解须使得:node.val * (N - node.val)值最大。

Submission

class Solution:
def maxProduct(self, root: TreeNode) -> int:
def getSumofNode(root: TreeNode) -> int:
if(root is None):
return 0
root.val += getSumofNode(root.left) + getSumofNode(root.right)
return root.val
# step1: get sum of given tree
N = getSumofNode(root)
res = 0
mod = 1000000007
# step2: traverse tree, to find maximum product
stack = []
tmp = root
while(len(stack) > 0 or tmp != None):
if(tmp != None):
stack.append(tmp)
tmp = tmp.left
else:
tmp = stack[-1]
stack.pop(-1)
res = max(res, tmp.val * (N - tmp.val))
tmp = tmp.right
# step3: do not forget the module operation
return res % mod



注意事项

  1. 本题中仅须对最终结果进行取余,而无需对中间结果进行取余(反而会得到错误的结果)。

发布于: 2020 年 06 月 05 日 阅读数: 24
用户头像

隔壁小王

关注

还未添加个人签名 2020.04.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 1339. Maximum Product of Splitted Binary Tree