分裂二叉树的最大乘积

🎯 问题描述

给你一棵二叉树，它的根为 root。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
（注意：需要在取模之前最大化乘积，而不是取模之后）

💻 解题思路

思路一：一次 DFS + 数组收集

核心思想：

通过一次 DFS 后序遍历，计算出每个节点为根的子树和，并全部存入数组 co_sum 中。
遍历结束后，数组中包含了所有可能切分出来的子树和。
遍历数组，利用公式 子树和 * (总和 - 子树和) 找出最大乘积。

代码实现

from typing import Optional

# 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 maxProduct(self, root: Optional[TreeNode]) -> int:
        mod = 10**9 + 7
        co_sum = []
        
        def dfs(node):
            if node is None:
                return 0
            # 后序遍历：计算以当前节点为根的子树和
            co = node.val + dfs(node.left) + dfs(node.right)
            co_sum.append(co)
            return co 
        
        total = dfs(root)  # 获取整棵树的总和
        # 遍历所有可能的子树和，找出最大乘积
        ans = max(num * (total - num) for num in co_sum)
        return ans % mod
````

### 思路二：两次 DFS（空间优化版）

**核心思想**：

1. 第一次 DFS：单纯计算整棵树的总和 `total`。
2. 第二次 DFS：再次遍历树，计算每个子树的和 `sub_sum`，并实时更新最大乘积 `max(sub_sum * (total - sub_sum))`。

- **优点**：不需要额外的数组来存储所有子树和，空间复杂度更低。

#### 代码实现

```python
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        mod = 10**9 + 7
        self.total = 0
        self.ans = 0
        
        # 第一次 DFS：计算总和
        def get_total(node):
            if not node: return 0
            self.total += node.val
            get_total(node.left)
            get_total(node.right)
        
        # 第二次 DFS：计算子树和并更新最大乘积
        def get_subtree_sum(node):
            if not node: return 0
            sub_sum = node.val + get_subtree_sum(node.left) + get_subtree_sum(node.right)
            self.ans = max(self.ans, sub_sum * (self.total - sub_sum))
            return sub_sum
        
        get_total(root)
        get_subtree_sum(root)
        return self.ans % mod

📊 性能分析

时间复杂度： $O(n)$ 。无论是你的解法还是两次 DFS 解法，每个节点都只被访问了常数次。
空间复杂度：
- 你的解法： $O(n)$ 。需要一个数组来存储所有节点的子树和。
- 两次 DFS 解法：O(h) $。$ h 为树的高度，主要为递归栈的空间开销，不需要额外的数组。