leetcode1339

 1 class Solution:
 2     def __init__(self):
 3         self.subTrees = []
 4         self.sums = 0
 5         self.memo = {}
 6     def preOrder(self,root):
 7         if root != None:
 8             self.sums += root.val
 9             self.subTrees.append(self.subTreeSum(root))
10             self.preOrder(root.left)
11             self.preOrder(root.right)
12 
13     def subTreeSum(self,root):
14         cur,left,right = 0,0,0
15         if root != None and root in self.memo:
16             return self.memo[root]
17         else:
18             cur = root.val if root != None else 0
19         if root != None and root.left != None and root.left in self.memo:
20             left = self.memo[root.left]
21         else:
22             left = self.subTreeSum(root.left) if root != None and root.left != None else 0
23         if root != None and root.right != None and root.right in self.memo:
24             right = self.memo[root.right]
25         else:
26             right = self.subTreeSum(root.right) if root != None and root.right != None else 0
27         cur = cur + left + right
28         self.memo[root] = cur
29         return cur
30 
31     def maxProduct(self, root: 'TreeNode') -> int:
32         self.preOrder(root)
33         #print(self.sums)
34         #print(self.subTrees)
35         result = 0
36         for i in range(len(self.subTrees)):
37             part1 = self.subTrees[i]
38             part2 = self.sums - part1
39             product = part1 * part2
40             result = max(result,product)
41         return result % (1000000007)

算法思路：二叉树遍历+memo缓存。

遍历二叉树(本题使用先序遍历)，同时计算每一棵子树的所有节点的和。使用缓存记录已经计算过的子树和，以加快算法的执行效率。

得到所有子树的和之后，用树所有节点的和减去任意一个子树的和，将原二叉树分为两部分。

计算这两部分的乘积，保留乘积的最大值。最终结果对1000000007取余，即为所求。