难度: Medium
给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：110 解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）
示例 2：
输入：root = [1,null,2,3,4,null,null,5,6] 输出：90 解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）
示例 3：
输入：root = [2,3,9,10,7,8,6,5,4,11,1] 输出：1025
示例 4：
输入：root = [1,1] 输出：1
提示：
50000 个节点，且至少有 2 个节点。[1, 10000] 之间。运行时间: 128 ms
内存: 35.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.max = 0
def maxProduct(self, root: TreeNode) -> int:
# 处理特殊情况
if not root:
return self.max
# 计算子树和
def dfs_sum(node):
if node:
if node.left:
dfs_sum(node.left)
node.val += node.left.val
if node.right:
dfs_sum(node.right)
node.val += node.right.val
dfs_sum(root)
total = root.val
# 计算最大乘积
def dfs_count(node):
if node:
if node.left:
a = node.left.val
b = total - node.left.val
self.max = max(self.max, a * b)
if a > b:
dfs_count(node.left)
if node.right:
a = node.right.val
b = total - node.right.val
self.max = max(self.max, a * b)
if a > b:
dfs_count(node.right)
dfs_count(root)
return self.max % (10 ** 9 + 7)
题解采用了深度优先搜索（DFS）的方法来解题。首先，通过一个DFS遍历计算出整棵树的总和，同时修改每个节点的值，使得每个节点存储的是该节点为根的子树的总和。接着，再次通过DFS遍历树，对于每个节点计算如果以该节点的子节点为分割点，分成的两棵子树的乘积，并更新最大乘积。最后返回经过模运算的最大乘积结果。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.max = 0
def maxProduct(self, root: TreeNode) -> int:
# 处理特殊情况
if not root:
return self.max
# 计算子树和的DFS
def dfs_sum(node):
if node:
if node.left:
dfs_sum(node.left)
node.val += node.left.val # 累加左子树的和
if node.right:
dfs_sum(node.right)
node.val += node.right.val # 累加右子树的和
dfs_sum(root)
total = root.val # 总和
# 计算最大乘积的DFS
def dfs_count(node):
if node:
if node.left:
a = node.left.val
b = total - node.left.val
self.max = max(self.max, a * b) # 更新最大乘积
if a > b:
dfs_count(node.left) # 递归计算更大子树
if node.right:
a = node.right.val
b = total - node.right.val
self.max = max(self.max, a * b) # 更新最大乘积
if a > b:
dfs_count(node.right) # 递归计算更大子树
dfs_count(root)
return self.max % (10 ** 9 + 7) # 返回结果并取模
这种方法主要是为了优化计算效率。通过首次DFS遍历，我们可以在遍历每个节点时即时计算并存储该节点为根的子树的总和。这样，当我们在第二次DFS遍历中需要计算以某个节点的子节点为分割点时，可以直接使用已存储的子树总和值，避免了重复的计算，从而显著提高了算法的效率。同时，这也简化了逻辑，因为我们只需要关注当前处理的节点和其子树的关系。
在第二次DFS遍历中，并不是选择特定的子节点作为分割点，而是对每个节点的所有子节点进行遍历，并计算以每个子节点为分割点的情况。对于不平衡的树，这种方法同样适用，因为算法本身不依赖于树的平衡性。我们通过递归地计算每个节点的左右子树的乘积，并更新最大乘积，这保证了无论树的形状如何，都能找到最大的乘积值。
更新节点值中的最大乘积是一种高效的策略，它避免了对所有可能分割点的重复计算和存储。通过维护一个全局最大值变量，并在每次计算分割产生的乘积后比较并更新这个变量，我们可以保持空间复杂度较低，同时快速得到最终结果。直接计算所有可能的乘积并存储会导致空间和时间复杂度增加，因为这需要额外的数据结构来存储所有子树的乘积结果，并从中查找最大值，这在大规模数据时尤其低效。