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)

约束条件：

  • 树中节点数目在范围 [2, 5 * 10^4] 内
  • 1 <= Node.val <= 10^4

提示：

  • 如果我们知道某个子树的和，答案就是 max((total_sum - subtree_sum) * subtree_sum) 在每个节点处的值。

解题思路

这道题的核心思路是：当我们删除一条边时，原树会被分成两个子树，我们要最大化这两个子树和的乘积。

解题思路：

  1. 两次遍历策略：首先通过一次 DFS 计算整棵树的总和，然后再次遍历时计算每个子树的和，并更新最大乘积。

  2. 关键观察：对于任意一个节点，如果我们切断它与父节点的连接，会得到两部分：

    • 以该节点为根的子树，和为 subtree_sum
    • 剩余部分，和为 total_sum - subtree_sum
    • 乘积为 (total_sum - subtree_sum) * subtree_sum

  3. 算法步骤：

    • 第一次 DFS：计算整棵树的总和
    • 第二次 DFS：遍历每个节点，计算以该节点为根的子树和，同时更新最大乘积

  4. 优化细节：为了避免整数溢出，我们使用 long long 类型进行计算，最后对结果取模。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(h)，其中 h 是树的高度。

代码实现

class Solution {
private:
    long long totalSum = 0;
    long long maxProd = 0;
    const int MOD = 1000000007;
    
public:
    int maxProduct(TreeNode* root) {
        // 第一次遍历：计算总和
        calculateSum(root);
        // 第二次遍历：寻找最大乘积
        dfs(root);
        return maxProd % MOD;
    }
    
private:
    long long calculateSum(TreeNode* node) {
        if (!node) return 0;
        totalSum += node->val;
        calculateSum(node->left);
        calculateSum(node->right);
        return totalSum;
    }
    
    long long dfs(TreeNode* node) {
        if (!node) return 0;
        
        long long leftSum = dfs(node->left);
        long long rightSum = dfs(node->right);
        long long currentSum = node->val + leftSum + rightSum;
        
        // 计算删除左子树边或右子树边的乘积
        if (node->left) {
            maxProd = max(maxProd, leftSum * (totalSum - leftSum));
        }
        if (node->right) {
            maxProd = max(maxProd, rightSum * (totalSum - rightSum));
        }
        
        return currentSum;
    }
};

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        MOD = 10**9 + 7
        
        # 第一次遍历：计算总和
        def calculate_sum(node):
            if not node:
                return 0
            return node.val + calculate_sum(node.left) + calculate_sum(node.right)
        
        total_sum = calculate_sum(root)
        max_product = 0
        
        # 第二次遍历：寻找最大乘积
        def dfs(node):
            nonlocal max_product
            if not node:
                return 0
            
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            current_sum = node.val + left_sum + right_sum
            
            # 计算删除左子树边或右子树边的乘积
            if node.left:
                max_product = max(max_product, left_sum * (total_sum - left_sum))
            if node.right:
                max_product = max(max_product, right_sum * (total_sum - right_sum))
            
            return current_sum
        
        dfs(root)
        return max_product % MOD

public class Solution {
    private long totalSum = 0;
    private long maxProduct = 0;
    private const int MOD = 1000000007;
    
    public int MaxProduct(TreeNode root) {
        // 第一次遍历：计算总和
        CalculateSum(root);
        // 第二次遍历：寻找最大乘积
        DFS(root);
        return (int)(maxProduct % MOD);
    }
    
    private long CalculateSum(TreeNode node) {
        if (node == null) return 0;
        totalSum += node.val;
        CalculateSum(node.left);
        CalculateSum(node.right);
        return totalSum;
    }
    
    private long DFS(TreeNode node) {
        if (node == null) return 0;
        
        long leftSum = DFS(node.left);
        long rightSum = DFS(node.right);
        long currentSum = node.val + leftSum + rightSum;
        
        // 计算删除左子树边或右子树边的乘积
        if (node.left != null) {
            maxProduct = Math.Max(maxProduct, leftSum * (totalSum - leftSum));
        }
        if (node.right != null) {
            maxProduct = Math.Max(maxProduct, rightSum * (totalSum - rightSum));
        }
        
        return currentSum;
    }
}

var maxProduct = function(root) {
    const MOD = 1000000007;
    let totalSum = 0;
    let maxProd = 0;
    
    // 第一次遍历：计算总和
    function calculateSum(node) {
        if (!node) return 0;
        totalSum += node.val;
        calculateSum(node.left);
        calculateSum(node.right);
        return totalSum;
    }
    
    // 第二次遍历：寻找最大乘积
    function dfs(node) {
        if (!node) return 0;
        
        const leftSum = dfs(node.left);
        const rightSum = dfs(node.right);
        const currentSum = node.val + leftSum + rightSum;
        
        // 计算删除左子树边或右子树边的乘积
        if (node.left) {
            maxProd = Math.max(maxProd, leftSum * (totalSum - leftSum));
        }
        if (node.right) {
            maxProd = Math.max(maxProd, rightSum * (totalSum - rightSum));
        }
        
        return currentSum;
    }
    
    calculateSum(root);
    dfs(root);
    return maxProd % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树两次，每次都是 O(n)
空间复杂度O(h)递归调用栈的深度，h 为树的高度，最坏情况下为 O(n)

相关题目