Description

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

---

1161. Maximum Level Sum of a Binary Tree

이진 트리의 root가 주어지며, 루트의 레벨은 1, 자식의 레벨은 2가 되고, 이런 식으로 계속됩니다.

노드의 값 합계가 최대가 되는 최소 레벨 x를 반환합니다.

예시 1:

입력: root = [1,7,0,7,-8,null,null]
출력: 2
설명:
레벨 1의 합 = 1.
레벨 2의 합 = 7 + 0 = 7.
레벨 3의 합 = 7 + -8 = -1.
따라서 최대 합을 가진 레벨인 2레벨을 반환합니다.

예시 2:

입력: root = [989,null,10250,98693,-89388,null,null,null,-32127]
출력: 2

제약 사항:

• 트리의 노드 수는 [1, 104] 범위에 있습니다.
• -105 <= Node.val <= 105

Solution

class Solution {
    public int maxLevelSum(TreeNode root) {
        List<Integer> levelSum = new ArrayList<>(); // 레벨별 합계 저장 리스트
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size(), sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val; // 현재 노드 값 합계에 추가
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            levelSum.add(sum); // 레벨별 합계 리스트에 추가
        }

        // 최대 합계를 가진 레벨 찾기
        int maxVal = Integer.MIN_VALUE, maxIndex = -1;
        for (int i = 0; i < levelSum.size(); i++) {
            if (levelSum.get(i) > maxVal) {
                maxVal = levelSum.get(i);
                maxIndex = i;
            }
        }

        return maxIndex + 1; // 1부터 시작하는 레벨로 조정
    }
}