LeetCode 题解工作台
分裂二叉树的最大乘积
给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。 示例 1： 输入： root = [1,2,3,4,5,6] 输出： 110 解释： 删除红色的边，得到 2 棵子树，和…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以用两次 DFS 来解决这个问题。 第一次，我们用一个 函数递归求出整棵树所有节点的和，记为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树，它的根为 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 来解决这个问题。
第一次，我们用一个 函数递归求出整棵树所有节点的和，记为 。
第二次，我们用一个 函数递归遍历每个节点，求出以当前节点为根的子树的节点和 ，那么当前节点与其父节点分裂后两棵子树的节点和分别为 和 ，它们的乘积为 ，我们遍历所有节点，求出乘积的最大值，即为答案。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# 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:
def sum(root: Optional[TreeNode]) -> int:
if root is None:
return 0
return root.val + sum(root.left) + sum(root.right)
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
t = root.val + dfs(root.left) + dfs(root.right)
nonlocal ans, s
if t < s:
ans = max(ans, t * (s - t))
return t
mod = 10**9 + 7
s = sum(root)
ans = 0
dfs(root)
return ans % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate an understanding of tree traversal techniques, especially DFS.
- question_mark
Look for clear reasoning behind subtree sum calculation and product maximization.
- question_mark
The candidate should show awareness of modular arithmetic for large numbers in the final result.
常见陷阱
外企场景- error
Failure to compute the total sum of the tree before starting to calculate the products for splits.
- error
Not efficiently managing memory or running into recursion depth issues for very large trees.
- error
Taking the modulo after computing the product instead of before, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Handle cases with very large trees (e.g., up to 50,000 nodes) efficiently.
- arrow_right_alt
Optimize the space usage when storing subtree sums to handle larger trees within memory constraints.
- arrow_right_alt
Consider alternative methods for maximizing the product, such as dynamic programming or iterative solutions.