LeetCode 1339. 分裂二叉树的最大乘积（DP）

Michael阿明

发布于 2020-07-13 16:11:22

4990

发布于 2020-07-13 16:11:22

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

给你一棵二叉树，它的根为 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
 
提示：
每棵树最多有 50000 个节点，且至少有 2 个节点。
每个节点的值在 [1, 10000] 之间。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-product-of-splitted-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. DP解题

class Solution {
public:
    int maxProduct(TreeNode* root) {
        int sum = subsum(root);//求每个节点的包含自己在内及子节点和
        unsigned long long maxProduct = 1;
        dfs(root,sum,maxProduct);//遍历树，对每个节点求 val*（sum-val）,取最大
        return int(maxProduct%1000000007);
    }

    int subsum(TreeNode* root)
    {
    	if(!root) return 0;
    	int l = subsum(root->left);//自底向上DP
    	int r = subsum(root->right);
    	root->val += l+r;
    	return root->val;
    }

    void dfs(TreeNode* root, int& sum, unsigned long long& maxProduct)
    {
    	if(!root || (!root->left && !root->right)) return;
    	unsigned long long product;
    	if(root->left)
    	{
    		product = (unsigned long long)root->left->val * (sum-root->left->val);
    		if(product > maxProduct)
    			maxProduct = product;
    	}
    	if(root->right)
    	{
    		product = (unsigned long long)root->right->val * (sum-root->right->val);
    		if(product > maxProduct)
    			maxProduct = product;
    	}
    	dfs(root->left,sum,maxProduct);
    	dfs(root->right,sum,maxProduct);
    }
};