给出一颗二叉树，问剪掉一条边，使得二叉树分成两颗之后，两棵树的节点和的乘积最大多少，结果mod 10
9 + 7
两遍DFS，第一遍计算所有节点总和，第二遍每搜一个节点就计算如果切掉连接这个节点和它的父节点的边所形成的两棵树的节点和乘积，更新全剧最大值
1 #1339
2 #Runtime: 479 ms
3 #Memory: 98.4 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def maxProduct(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 def DFS_total_sum(r):
18 if not r:
19 return 0
20 return r.val + DFS_total_sum(r.left) + DFS_total_sum(r.right)
21 total_sum = DFS_total_sum(root)
22 self.ans = 0
23 def DFS_max_product(r):
24 if not r:
25 return 0
26 cur_sum = r.val + DFS_max_product(r.left) + DFS_max_product(r.right)
27 self.ans = max(self.ans, (total_sum - cur_sum) * cur_sum)
28 return cur_sum
29 DFS_max_product(root)
30 return self.ans % (10**9 + 7)