LeetCode 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 tt）乘以s u m − t sum-tsum−t（其中s u m sumsum是所有节点元素之和）。

• 时间复杂度O ( s i z e ( t r e e ) ) O(size(tree))O(size(tree))
• 空间复杂度O ( s i z e ( t r e e ) ) O(size(tree))O(size(tree))

AC代码

C++

/* * @LastEditTime: 2026-01-07 21:52:59 */typedeflonglongll;classSolution{private:vector<int>subTreeSum;intdfs(TreeNode*root){intleftSum=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);}returnroot->val+leftSum+rightSum;}public:intmaxProduct(TreeNode*root){inttotalSum=dfs(root);ll ans=0;for(intt:subTreeSum){ans=max(ans,(ll)t*(totalSum-t));}returnans%1000000007;}};

Python

''' LastEditTime: 2026-01-07 21:55:18 '''fromtypingimportOptional# 昨天改的newSolutions.py(好像是)今天就用上了classSolution:defdfs(self,root:TreeNode)->int:left,right=0,0ifroot.left:left=self.dfs(root.left)self.sum.append(left)ifroot.right:right=self.dfs(root.right)self.sum.append(right)returnroot.val+left+rightdefmaxProduct(self,root:Optional[TreeNode])->int:self.sum=[]sum=self.dfs(root)returnmax(t*(sum-t)fortinself.sum)%1000000007

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

千篇源码题解已开源