1339. Maximum Product of Splitted Binary Tree

leetcode medium

#csharp#leetcode#math#medium#tree#two-pointers

Task

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

Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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
}

Explanation

Algorithm

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

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

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

😎