1339. Maximum Product of Splitted Binary Tree

LeetCode medium original: C# #csharp #leetcode #math #medium #tree #two-pointers

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

given корневое 树. Разделите бинарное 树 на два поддерева, удалив одно edge так, чтобы произведение сумм поддеревьев было максимальным.

return максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, return его по модулю 10^9 + 7.

Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.

示例:

Input: root = [1,2,3,4,5,6]

Output: 110

Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

C# 解法

匹配/原始

public class Solution {
    private List<int> allSums = new List<int>();
    
    public int MaxProduct(TreeNode root) {
        long totalSum = TreeSum(root);
        long best = 0;
        foreach (long sum in allSums) {
            best = Math.Max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }
    private int TreeSum(TreeNode subroot) {
        if (subroot == null) return 0;
        int leftSum = TreeSum(subroot.left);
        int rightSum = TreeSum(subroot.right);
        int totalSum = leftSum + rightSum + subroot.val;
        allSums.Add(totalSum);
        return totalSum;
    }
}

C++ 解法

自动草稿，提交前请检查

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private List<int> allSums = new List<int>();
    
    public int MaxProduct(TreeNode root) {
        long totalSum = TreeSum(root);
        long best = 0;
        foreach (long sum in allSums) {
            best = max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }
    private int TreeSum(TreeNode subroot) {
        if (subroot == null) return 0;
        int leftSum = TreeSum(subroot.left);
        int rightSum = TreeSum(subroot.right);
        int totalSum = leftSum + rightSum + subroot.val;
        allSums.push_back(totalSum);
        return totalSum;
    }
}

Java 解法

匹配/原始

class Solution {

    private List<Integer> allSums = new ArrayList<>();

    public int maxProduct(TreeNode root) {
        long totalSum = treeSum(root);
        long best = 0;
        for (long sum : allSums) {
            best = Math.max(best, sum * (totalSum - sum));
        }
        return (int)(best % 1000000007);
    }

    private int treeSum(TreeNode subroot) {
        if (subroot == null) return 0;
        int leftSum = treeSum(subroot.left);
        int rightSum = treeSum(subroot.right);
        int totalSum = leftSum + rightSum + subroot.val;
        allSums.add(totalSum);
        return totalSum;
    }
}

Python 解法

匹配/原始

class Solution:
    def __init__(self):
        self.all_sums = []

    def maxProduct(self, root):
        total_sum = self.treeSum(root)
        best = 0
        for s in self.all_sums:
            best = max(best, s * (total_sum - s))
        return best % 1000000007

    def treeSum(self, subroot):
        if not subroot:
            return 0
        left_sum = self.treeSum(subroot.left)
        right_sum = self.treeSum(subroot.right)
        total_sum = left_sum + right_sum + subroot.val
        self.all_sums.append(total_sum)
        return total_sum

Go 解法

匹配/原始

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Solution struct {
    allSums []int
}

func (s *Solution) MaxProduct(root *TreeNode) int {
    totalSum := s.treeSum(root)
    var best int64 = 0
    for _, sum := range s.allSums {
        best = max(best, int64(sum)*(int64(totalSum)-int64(sum)))
    }
    return int(best % 1000000007)
}

func (s *Solution) treeSum(subroot *TreeNode) int {
    if subroot == nil {
        return 0
    }
    leftSum := s.treeSum(subroot.Left)
    rightSum := s.treeSum(subroot.Right)
    totalSum := leftSum + rightSum + subroot.Val
    s.allSums = append(s.allSums, totalSum)
    return totalSum
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

Algorithm

Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке.

Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева.

find максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。