专栏首页Michael阿明学习之路LeetCode 1339. 分裂二叉树的最大乘积(DP)

LeetCode 1339. 分裂二叉树的最大乘积(DP)

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);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • LeetCode 114. 二叉树展开为链表(递归)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-link...

    Michael阿明
  • LeetCode 687. 最长同值路径(二叉树,递归)

    给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

    Michael阿明
  • 【leetcode】Sum Root to Leaf Numbers

    Given a binary tree containing digits from 0-9 only, each root-to-leaf path coul...

    阳光岛主
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014
  • admin3

    #################################################### 真机上实现别名的定义,修改配置文件

    py3study
  • 《调教命令行04》触碰Linux的每个角落(长文)

    想要了解一个人,就先要了解他的灵魂。可是别说是灵魂了,就连一个真心的笑容,你在生活中也很难见到。更多的是菩萨手段,修罗心肠。很多人喜欢孩子的原因,就是因为他们悲...

    xjjdog
  • centos7系统常用命令

    https://blog.csdn.net/weixin_39951988/article/details/87613816#2.5%C2%A0which%E5...

    GH
  • 【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

    深度学习技术前沿公众号博主
  • leecode刷题(24)-- 翻转二叉树

    二叉树问题,我们首先要想到的使用递归的方式来解决,有了这个思路,处理这道问题就很简单了:先互换根节点的左右节点,然后递归地处理左子树,再递归地处理右子树,直到所...

    希希里之海

扫码关注云+社区

领取腾讯云代金券