Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
Example 2:
Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)
Example 3:
Input: root = [2,3,9,10,7,8,6,5,4,11,1] Output: 1025
Example 4:
Input: root = [1,1] Output: 1
Constraints:
- Each tree has at most
50000nodes and at least2nodes. - Each node's value is between
[1, 10000].
---------------------------------------------------------------------------------
担心递归会超时，写了一个非递归的。对于非递归来说，layersorder，parent, subsum这几个是必须的，但是忘了更新layers
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxProduct(self, root):
layerorder = [root]
parent,subsum = {root:None},{root:0} #bug1: {root,None}
layers= [[root],[]]
c,n = 0,1
while (layers[c]):
for node in layers[c]:
for child in [node.left, node.right]:
if (child != None):
layers[n].append(child) #bug2: miss this line
layerorder.append(child)
parent[child]=node
subsum[child]=0
layers[c].clear()
c,n = n,c
for node in layerorder[::-1]:
subsum[node] += node.val
p = parent[node]
if (p != None):
subsum[p] += subsum[node]
total,maxv,maxi = subsum[root],subsum[root]*2,root
for i in range(1,len(layerorder)):
diff = abs(subsum[layerorder[i]]*2-total)
if (diff < maxv):
maxv = diff
maxi = layerorder[i]
return (total-subsum[maxi])*subsum[maxi]%1000000007
s = Solution()
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n1.left,n1.right = n2,n3
n2.left,n2.right = n4,n5
n3.left = n6
print(s.maxProduct(n1))