🌲 초보자를 위한 가이드 'Maximum Level Sum of a Binary Tree' – LeetCode 1161 (C++, Python, JavaScript)

I’m happy to translate the article for you, but I’ll need the actual text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the text, I’ll keep the source link unchanged and translate the rest into Korean while preserving the original formatting and markdown.

문제 요약

이진 트리의 root가 주어집니다. 각 노드는 정수 값을 저장하고 있습니다.
루트는 레벨 1, 그 자식들은 레벨 2, 이런 식으로 레벨이 증가합니다.

목표:
노드 값들의 합이 최대인 레벨 번호를 반환합니다.
여러 레벨이 동일한 최대 합을 가질 경우, 가장 작은(즉, 가장 높은) 레벨 번호를 반환합니다.

예시

Input:  root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1
Level 2 sum = 7 + 0 = 7
Level 3 sum = 7 + (-8) = -1
→ The maximum sum is 7, occurring at level 2.

설명:
레벨 1의 합은 1, 레벨 2의 합은 7 + 0 = 7, 레벨 3의 합은 7 + (-8) = -1입니다.
→ 최대 합은 7이며, 이는 레벨 2에서 발생합니다.

직관

트리를 레벨별로 살펴보는 가장 자연스러운 방법은 너비 우선 탐색(BFS) 입니다.
하나의 가지를 깊게 파고들기보다는, BFS는 큐를 사용해 현재 “층”에 있는 모든 노드를 처리한 뒤 다음 층으로 이동합니다.

알고리즘 개요

1. 루트 노드로 큐를 초기화합니다.
2. 큐가 비어 있지 않은 동안:
   • 현재 큐 크기를 기록 → 이 레벨에 있는 노드 수.
   • 각 노드를 dequeue하고, 그 값을 levelSum에 누적한 뒤, null이 아닌 자식들을 enqueue합니다.
   • 레벨 처리가 끝나면 levelSum을 지금까지 본 최댓값과 비교하고, 필요하면 답을 업데이트합니다.
3. 최대 합을 만든 레벨 인덱스를 반환합니다.

BFS는 O(N) 시간(각 노드를 한 번씩 방문)과 O(W) 추가 공간을 보장합니다. 여기서 W는 트리의 최대 너비(가장 큰 레벨의 크기)입니다.

코드 블록

C++

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 0;

        long long maxSum   = LLONG_MIN;   // handles negative values
        int       maxLevel = 1;
        int       curLevel = 1;

        queue q;
        q.push(root);

        while (!q.empty()) {
            int   sz       = q.size();
            long long levelSum = 0;

            for (int i = 0; i val;

                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }

            if (levelSum > maxSum) {
                maxSum   = levelSum;
                maxLevel = curLevel;
            }
            ++curLevel;
        }
        return maxLevel;
    }
};

파이썬

from collections import deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        max_sum   = float('-inf')
        max_level = 1
        cur_level = 1

        q = deque([root])

        while q:
            level_sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                level_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            if level_sum > max_sum:
                max_sum   = level_sum
                max_level = cur_level

            cur_level += 1

        return max_level

자바스크립트

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
    if (!root) return 0;

    let maxSum   = -Infinity;
    let maxLevel = 1;
    let curLevel = 1;

    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;
        let levelSum = 0;

        for (let i = 0; i  maxSum) {
            maxSum   = levelSum;
            maxLevel = curLevel;
        }
        ++curLevel;
    }

    return maxLevel;
};

Key Takeaways

• **Breadth‑First Search (BFS)**는 “레벨‑순서” 트리 문제에 가장 적합한 기법이다.
• queue(또는 Python의 deque)를 사용하면 각 레벨을 노드당 O(1) 평균 시간으로 처리할 수 있다.
• 노드 값이 음수일 수 있으므로 “최대 합”을 가장 작은 값(LLONG_MIN, -Infinity, 또는 -inf)으로 초기화한다.
• 시간 복잡도: O(N), 여기서 N은 노드 수이다.
• 공간 복잡도: O(W), 여기서 W는 트리의 최대 너비이며(완전 균형 트리의 최악 경우 O(N)).

최종 생각

이 문제는 대규모 시스템에서 나타나는 트리 순회 패턴을 소개하는 훌륭한 입문서입니다:

• 검색 엔진 인덱싱은 종종 BFS와 유사한 크롤러를 사용하여 홈페이지에서 시작해 페이지를 레벨별로 탐색하며, 가장 “중요한”(최상위) 콘텐츠가 먼저 처리되도록 합니다.
• 소셜 네트워크 분석에서는 가장 활동이 많은 레벨을 찾는 것이 “최대 레벨 합” 개념을 반영하며, 가장 영향력 있는 사용자 “층”을 식별하는 것과 같습니다.

BFS와 큐 관리에 능숙해지면 다양한 실제 그래프 및 트리 문제를 해결할 수 있는 역량을 갖추게 됩니다. 코딩을 즐기세요!

가장 유망한 분리 차수 식별

그래프 분석에서 가장 많은 잠재적 연결을 포함하는 **“degree of separation”**을 식별하는 것은 중요한 단계입니다. Breadth‑First Search (BFS) 를 숙달하는 것은 Google이나 Meta와 같은 기업의 기술 면접에서 핵심 요구 사항입니다.