[LeetCode] 1339. Maximum Product of Splitted Binary Tree

문제 출처: https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/

Maximum Product of Splitted Binary Tree - LeetCode

---

문제

이진트리의 루트가 주어지면, 하위 트리 합의 곱이 최대가 되도록 한 간선을 제거하여 두 개의 하위 트리로 분리하라.

두 하위트리 합계의 곱이 가질 수 있는 최대 값을 반환하라. 답이 매우 클지도 모르기 때문에 10^9+7로 나눈 나머지를 반환하라.

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)

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

Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

---

풀이

트리에서 임의의 간선을 잘라 두 트리를 만들 때, 해당 트리들의 합을 어떻게 구할 수 있을까.

 

만약 자르기 전의 원래 트리의 총합을 알고 있다고 한다면, 두 트리 중에서 한 개의 트리의 합을 구하면 나머지 트리의 합을 알 수 있다.

위 그림과 같이 노드 합계가 21인 트리가 있고, 빨간 간선을 기준으로 두 개의 트리를 나눈다고 해보자. 빨간 선을 기준으로 나눌 때, 노드 1을 루트로 하는 트리와 노드 2를 루트로 하는 트리가 생기게 된다. 두 트리 중에서 노드 2를 기준으로 하는 트리의 합계를 구하면 11이 되는데, 이때 자동적으로 나머지 트리의 노드 합계는 21 - 11 = 10이 된다.

 

이러한 규칙을 이용하여 트리 내의 모든 간선을 대상으로 두 개의 트리로 나누고, 나누어진 두 트리의 합계를 곱하여 그중 최댓값을 찾는 방식으로 문제를 풀 수 있다.

 

트리 순회 알고리즘이 호출되는 횟수를 최소화 하기 위해서 각 노드를 루트로 하는 서브 트리의 합을 미리 구해놓을 수 있다. 다음 그림과 같은 작업을 수행하는 것이다.

var buildTree = function(root) {
    const node = new TreeNode();

    node.left = root.left ? buildTree(root.left) : null;
    node.right = root.right ? buildTree(root.right) : null;

    node.val = root.val + (node.left ? node.left.val : 0) + (node.right ? node.right.val : 0);

    return node;
}

이렇게 트리를 구축하게 되면 단순하게 이 트리를 순회하면서 "(트리의 루트 노드의 값 - 방문한 노드의 값) * 방문한 노드의 값"을 계산하는 것만으로 한 개의 간선을 제거했을 때 얻을 수 있는 두 하위 트리 노드 합계의 곱을 계산할 수 있다. 코드는 다음과 같다.

var maxProduct = function(root) {
    const sumTree = buildTree(root);
    const totalSum = sumTree.val;
    const MOD = 1000000007;

    let maxVal = 0;
    function findMaxProduct(root) {
        if (!root) { return; }

        const cutLeft = root.left ? (totalSum - root.left.val) * root.left.val : 0;
        const cutRight = root.right ? (totalSum - root.right.val) * root.right.val : 0;

        maxVal = Math.max(maxVal, cutLeft, cutRight);

        findMaxProduct(root.left);
        findMaxProduct(root.right);
    }

    findMaxProduct(sumTree);

    return maxVal % MOD;
};

 

Github: 1339.js

GitHub - opwe37/Algorithm-Study