1339. 分裂二叉树的最大乘积-深度优先遍历
2023-09-14 09:06:52 时间
1339. 分裂二叉树的最大乘积
给你一棵二叉树,它的根为 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
这题还是很有趣的,建议先求出树的总体和,然后遍历每个子树,再计算最大值就可以了,很不错的题目
解题代码如所示:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int sum_root(struct TreeNode* root){
if(root){
int a=sum_root(root->left);
int b=sum_root(root->right);
return a+b+root->val;
}
else{
return 0;
}
}
long long max;
long long find_max(struct TreeNode* root,int sum){
if(root){
long long a=find_max(root->left,sum);
long long b=find_max(root->right,sum);
long long maxt1=(sum-a)*a;
long long maxt2=(sum-b)*b;
max=fmax(max,fmax(maxt1,maxt2));
return a+b+root->val;
}
else{
return 0;
}
}
int maxProduct(struct TreeNode* root){
int sum=sum_root(root);
printf(" sum %d ",sum);
max=0;
long long s=find_max(root,sum);
return max%1000000007;
}
相关文章
- 二叉树的层序遍历,蛇形打印二叉树
- 森林转换成二叉树以及二叉树还原为森林代码
- Java实现 LeetCode 226 翻转二叉树
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Lintcode---二叉树的最大深度
- 二叉树遍历
- LeetCode:111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy
- Java二叉树实现及递归与非递归遍历实现
- 【二叉树】LeetCode 102. 二叉树的层序遍历【中等】
- LeetCode(106):从中序与后序遍历序列构造二叉树
- LeetCode(105):从前序与中序遍历序列构造二叉树
- 104. 二叉树的最大深度
- 【平衡二叉树】平衡二叉树的概念及相关操作
- 1448. 统计二叉树中好节点的数目-深度优先遍历+最大值传递
- 面试题 04.03. 特定深度节点链表-二叉树中序遍历反转
- 剑指 Offer II 045. 二叉树最底层最左边的值-中序遍历+全局变量解决
- 623. 在二叉树中增加一行-深度优先遍历
- [LeetCode] 114. 二叉树展开为链表 ☆☆☆(深度遍历)
- 算法 dfs —— 将二叉树 先序遍历 转为 链表
- 【Leetcode刷题Python】145. 二叉树的后序遍历
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【LeetCode】102. 二叉树的层序遍历
- 【C++要笑着学】搜索二叉树 (SBTree) | K 模型 | KV 模型