Leetcode 1339:分裂二叉树的最大乘积(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1339:分裂二叉树的最大乘积(超详细的解法!!!)

in leetcode with 0 comment

给你一棵二叉树,它的根为 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

提示:

解题思路

树形问题首先思考递归解。对于每个节点来说,我们分别考虑删除其左连接和删除其右连接的解,然后取其最大值即可。

通过递归我们可以直到删除左连接后,左边子树的和l;删除右连接后,右边子树的和r。那么,删除左连接后的解就是l*(total - l);删除右连接后的解就是r*(total - r)total表示整棵树的和,通过遍历二叉树求得)。

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        total = 0
        def inOrder(node):
            nonlocal total
            if node:
                inOrder(node.left)
                total += node.val
                inOrder(node.right)
        inOrder(root)
        
        mod, res = 10**9 + 7, 0
        def dfs(node):
            nonlocal res
            if not node:
                return 0
            
            l, r = dfs(node.left), dfs(node.right)
            res =  max(res, l * (total - l), r * (total - r))
            return l + r + node.val
        
        dfs(root)
        return res % mod

实际上代码可以更加简洁。我们的dfs函数返回值就是以root为根的树的和,那么我们只需要调用两次dfs函数即可。

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        total, mod, res = 0, 10**9 + 7, 0
        def dfs(node):
            nonlocal res
            if not node:
                return 0
            
            l, r = dfs(node.left), dfs(node.right)
            res =  max(res, l * (total - l), r * (total - r))
            return l + r + node.val
        
        total = dfs(root)
        dfs(root)
        return res % mod

reference:

https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/discuss/496549/JavaC%2B%2BPython-Easy-and-Concise

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses