給出一顆二叉樹，問剪掉一條邊，使得二叉樹分成兩顆之后，兩棵樹的節點和的乘積最大多少，結果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)