1339.分裂二叉树的最大乘积：深度优先搜索(一次DFS+存数组并遍历)

【LetMeFly】1339.分裂二叉树的最大乘积：深度优先搜索(一次DFS+存数组并遍历)

力扣题目链接：https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree/

给你一棵二叉树，它的根为 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] 之间。

解题方法：DFS

一次DFS遍历结束立刻得到答案似乎是不可行的（往左子遍历时需要右子和信息），但是我们可以在遍历时把所有子树的和存下来。

任意位置切一刀，就相当于以被切的子节点为根的子树的和（记为$t$）乘以$sum-t$（其中$sum$是所有节点元素之和）。

• 时间复杂度$O(size(tree))$
• 空间复杂度$O(size(tree))$

AC代码

C++

/*
 * @LastEditTime: 2026-01-07 21:52:59
 */
typedef long long ll;
class Solution {
private:
    vector<int> subTreeSum;
    int dfs(TreeNode* root) {
        int leftSum = 0, rightSum = 0;
        if (root->left) {
            leftSum = dfs(root->left);
            subTreeSum.push_back(leftSum);
        }
        if (root->right) {
            rightSum = dfs(root->right);
            subTreeSum.push_back(rightSum);
        }
        return root->val + leftSum + rightSum;
    }
public:
    int maxProduct(TreeNode* root) {
        int totalSum = dfs(root);
        ll ans = 0;
        for (int t : subTreeSum) {
            ans = max(ans, (ll)t * (totalSum - t));
        }
        return ans % 1000000007;
    }
};

Python

'''
LastEditTime: 2026-01-07 21:55:18
'''
from typing import Optional  # 昨天改的newSolutions.py(好像是)今天就用上了

class Solution:
    def dfs(self, root: TreeNode) -> int:
        left, right = 0, 0
        if root.left:
            left = self.dfs(root.left)
            self.sum.append(left)
        if root.right:
            right = self.dfs(root.right)
            self.sum.append(right)
        return root.val + left + right
    
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.sum = []
        sum = self.dfs(root)
        return max(t * (sum - t) for t in self.sum) % 1000000007

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源