給出一顆二叉樹，問剪掉一條邊，使得二叉樹分成兩顆之后，兩棵樹的節(jié)點(diǎn)和的乘積最大多少，結(jié)果mod 10
9 + 7
兩遍DFS，第一遍計(jì)算所有節(jié)點(diǎn)總和，第二遍每搜一個(gè)節(jié)點(diǎn)就計(jì)算如果切掉連接這個(gè)節(jié)點(diǎn)和它的父節(jié)點(diǎn)的邊所形成的兩棵樹的節(jié)點(diǎn)和乘積，更新全劇最大值
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)