1.题目描述
给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。 示例 2：
2.思路（dfs）
1.记二叉树中所有元素的值之和为 sum_r。 2.假设我们删除的边的两个端点为 u 和 v，其中 u 是 v 的父节点，那么在这条边删除之后，其中的一棵子树以 v 为根节点，记其中所有元素之和sum_v；另一棵子树以原二叉树的根节点 root 为根节点，其中元素之和为 sum_r - sum_v。我们需要找到一个节点 v，使得 (sum_v) * (sum_r - sum_v) 的值最大。 3.那么我们如何找到这个节点呢？我们首先使用深度优先搜索计算出 sum_r，即遍历二叉树中的每一个节点，将其对应的元素值进行累加。随后我们再次使用深度优先搜索，通过递归的方式计算出每一个节点 v 对应的子树元素之和 sum_v，并求出所有 (sum_v) * (sum_r - sum_v) 中的最大值，就可以得到答案。
3.代码
class Solution {
public:
void dfs(TreeNode
* root
, long long& sum
){
if(root
== NULL){
return;
}
sum
+= root
->val
;
dfs(root
->left
, sum
);
dfs(root
->right
, sum
);
}
int findMax(TreeNode
* root
){
if(root
== NULL){
return 0;
}
int currSum
= root
->val
+ findMax(root
->left
) + findMax(root
->right
);
maxval
= max((long long)currSum
*(allSum
- currSum
), maxval
);
return currSum
;
}
int maxProduct(TreeNode
* root
) {
dfs(root
, allSum
);
findMax(root
);
return maxval
% 1000000007;
}
private:
long long allSum
= 0;
long long maxval
= 0;
};
4.复杂度分析
时间复杂度：O(N)，其中 N 是二叉树的节点个数。 空间复杂度：O(1)。
