LeetCode 1339. Maximum Product of Splitted Binary Tree

关注

发布于: 2020 年 06 月 05 日

DescriptionGiven 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
﻿
题意分析根据题意，首先需要求得树中每个节点及其所在子树的节点和；
去除某个辺，等同于：去除某个节点，及其子树。因此需要遍历二叉树，找到最优解即可。
对于节点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
﻿
注意事项本题中仅须对最终结果进行取余，而无需对中间结果进行取余（反而会得到错误的结果）。