1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
private int totalSum;
private long ans;
public int maxProduct(TreeNode root) {
totalSum = helper(root);
dfs(root);
return (int) (ans % (1000000007));
}
private int helper(TreeNode node) {
if (node == null)
return 0;
return node.val + helper(node.left) + helper(node.right);
}
private int dfs(TreeNode node) {
if (node == null)
return 0;
long leftSum = dfs(node.left);
long rightSum = dfs(node.right);
ans = Math.max(ans, Math.max(leftSum * (totalSum - leftSum), rightSum * (totalSum - rightSum)));
return node.val + (int) leftSum + (int) rightSum;
}
}
|
先得到所有node的和. 然后dfs每个node. 假设它的左edge要断, 算一下此时的product, 然后假设右edge要断, 算一下product. 最后当遍历完每个node的时候, 我们把每个edge也都断了一遍. 从这里面找到最大product即可.
时间复杂度: O(n)
空间复杂度: O(n) 递归需要用栈.
