🌳 초보자 친화 가이드 ‘Maximum Product of Splitted Binary Tree’ – LeetCode 1339 (C++, Python, JavaScript)

Source: Dev.to

이진 트리는 재귀적인 특성 때문에 종종 위협적으로 느껴집니다. 하지만 많은 트리 문제는 단일 노드가 전체 구조와 어떻게 연결되는지를 살펴보는 것만으로도 해결할 수 있습니다. 이 가이드에서는 수학적 곱을 최대화하기 위해 “간선 하나를 자르는” 방법을 배워보겠습니다.

Problem Statement

당신에게 주어진 것은:

• 각 노드가 정수 값을 갖는 이진 트리의 루트.

당신의 목표:

1. 정확히 하나의 간선을 제거하여 트리를 두 개의 별도 서브트리로 나눈다.
2. 두 개의 결과 트리 각각에 있는 노드들의 합을 계산한다.
3. 이 두 합의 곱을 최대화하고, 그 결과를 (10^9 + 7) 로 mod 한 값을 반환한다.

직관

이 문제는 두 서브트리의 합을 곱했을 때 가능한 한 크게 만들 수 있는 두 수를 찾는 것입니다.
트리의 모든 노드의 총합을 (S) 라고 하고, 어떤 서브트리의 합을 (x) 라고 하면, 트리의 나머지 부분의 합은 (S - x) 가 됩니다.

최대 곱을 얻기 위해서는 다음과 같이 하면 됩니다:

1. 전체 합 계산 – 트리를 한 번 전체 순회하여 (S) 를 구합니다.
2. 가능한 모든 분할 평가 – 각 간선은 부모와 서브트리를 연결합니다. 그 간선을 끊으면 서브트리 합 (x) 가 얻어집니다.
3. 곱 계산 – 각 서브트리 합에 대해 (x \times (S - x)) 를 계산합니다.
4. 최대값 추적 – 순회하면서 가장 큰 곱을 기록합니다.

후위 순회(왼쪽, 오른쪽, 현재 노드)는 각 노드가 자신의 자식들의 합을 먼저 알 수 있게 해 주므로 여기서 완벽하게 사용됩니다.

코드

C++

class Solution {
public:
    const long long MOD = 1e9 + 7;
    long long total = 0;   // total sum of all nodes
    long long ans   = 0;   // best product found

    // First pass – compute total sum
    void calculateTotal(TreeNode* root) {
        if (!root) return;
        total += root->val;
        calculateTotal(root->left);
        calculateTotal(root->right);
    }

    // Second pass – post‑order, compute subtree sums and update answer
    long long subTreeSum(TreeNode* root) {
        if (!root) return 0;

        long long leftSum  = subTreeSum(root->left);
        long long rightSum = subTreeSum(root->right);

        // If we cut the edge to the left child
        ans = max(ans, leftSum * (total - leftSum));
        // If we cut the edge to the right child
        ans = max(ans, rightSum * (total - rightSum));

        return leftSum + rightSum + root->val;
    }

    int maxProduct(TreeNode* root) {
        calculateTotal(root);      // O(N)
        subTreeSum(root);          // O(N)
        return ans % MOD;
    }
};

파이썬

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.total = 0          # total sum of all nodes
        self.ans   = 0          # best product found

        # First pass – compute total sum
        def get_total(node):
            if not node:
                return
            self.total += node.val
            get_total(node.left)
            get_total(node.right)

        # Second pass – post‑order, compute subtree sums and update answer
        def get_subtree_sum(node):
            if not node:
                return 0

            left_sum  = get_subtree_sum(node.left)
            right_sum = get_subtree_sum(node.right)

            cur_sum = left_sum + right_sum + node.val
            # Update max product (do NOT mod yet)
            self.ans = max(self.ans, cur_sum * (self.total - cur_sum))
            return cur_sum

        get_total(root)          # O(N)
        get_subtree_sum(root)    # O(N)

        return self.ans % (10**9 + 7)

자바스크립트

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxProduct = function (root) {
    let total = 0;   // total sum of all nodes
    let ans   = 0;   // best product found

    // First pass – compute total sum
    const getTotal = (node) => {
        if (!node) return;
        total += node.val;
        getTotal(node.left);
        getTotal(node.right);
    };

    // Second pass – post‑order, compute subtree sums and update answer
    const getSubtreeSum = (node) => {
        if (!node) return 0;

        const leftSum  = getSubtreeSum(node.left);
        const rightSum = getSubtreeSum(node.right);
        const curSum   = leftSum + rightSum + node.val;

        const product = curSum * (total - curSum);
        if (product > ans) ans = product;

        return curSum;
    };

    getTotal(root);          // O(N)
    getSubtreeSum(root);     // O(N)

    // Use BigInt for safety before applying modulo
    return Number(BigInt(ans) % 1000000007n);
};

Key Takeaways

• Post‑order traversal 은 노드의 계산이 자식에 의존할 때 이상적이다 (여기서는 서브트리 합이 필요함).
• Two‑pass strategy 는 문제를 단순화하는 경우가 많다: 먼저 전역 정보(전체 합)를 수집하고, 그 다음 핵심 로직(곱 계산)을 수행한다.
• Maximize before modulo – 모듈러 연산을 너무 일찍 적용하면 곱의 순서가 바뀌어 잘못된 답이 나올 수 있다.

최종 생각

멘토로서 저는 학생들이 트리 문제에서 모든 가능한 분할을 한 번에 시각화하려다 보니 어려움을 겪는 모습을 자주 봅니다. 대신 어떤 간선을 자르면 전체 서브트리가 격리된다는 특성에 집중하세요. 문제를 “각 서브트리의 합은 무엇인가?” 로 축소하고 간단한 post‑order walk를 사용하면 해결책이 직관적이면서도 효율적이 됩니다. 즐거운 코딩 되세요! 🚀

트리에서의 재귀 합

단일 노드:
“내 아래 모든 것의 합을 알면, 나머지 트리의 합을 결정할 수 있다.”

이 논리는 네트워크 라우팅 알고리즘의 기본이며, 엔지니어가 트래픽을 분할할 최적 위치를 찾거나 병목 노드를 식별해야 할 때 중요합니다. 또한 데이터 과학에서 계층적 클러스터링과도 매우 관련이 있습니다.

이러한 재귀 패턴을 마스터하면 훨씬 더 효율적인 소프트웨어 엔지니어가 될 수 있습니다.