1161. Maximum Level Sum of a Binary Tree

Maximum Level Sum of a Binary Tree - LeetCode

이진 트리의 루트 노드가 주어질 때, 각 레벨에 있는 노드 값의 합이 최대인 레벨 x를 반환합니다.

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.

 

Example 1:

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.
So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

문제 요약: 

주어진 이진 트리에서 각 레벨의 노드 값 합이 최대인 레벨을 찾는 문제입니다.

풀이 과정:

1. 각 레벨의 노드 값 합을 저장하기 위한 배열 levelSum을 초기화합니다.
2. BFS (너비 우선 탐색)를 사용하여 이진 트리를 순회하면서 각 레벨의 노드 값을 합산하여 levelSum 배열에 저장합니다.
3. 이진 트리 순회를 위한 큐를 생성하고, 루트 노드를 큐에 추가합니다.
4. 반복문을 통해 큐가 비어질 때까지 다음을 수행합니다:
   a. 현재 레벨의 노드 수를 확인하기 위해 현재 큐의 크기를 얻습니다.
   b. 현재 레벨의 노드 값을 모두 더하여 해당 레벨의 합을 계산합니다.
   c. 레벨 값 x가 levelSum 배열의 길이를 초과하면, 배열 크기를 늘립니다.
   d. 현재 레벨의 합을 levelSum 배열의 인덱스 x-1에 추가합니다.
   e. 현재 레벨의 모든 노드를 큐에서 제거하고 다음 레벨의 노드를 큐에 추가합니다.
5. levelSum 배열에서 최대값을 찾고, 해당 값의 인덱스에 1을 더한 값을 반환합니다.

class Solution {
    public int maxLevelSum(TreeNode root) {
        if (root == null) return 0;
        
        int maxSum = Integer.MIN_VALUE;
        int maxLvl = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int lvl = 0;
        while(!queue.isEmpty()){
            int queSize = queue.size();
            int sum = 0;
            lvl++;
            for(int i = 0; i < queSize; i++){
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            
            if(sum > maxSum){
                maxSum = sum;
                maxLvl = lvl;
            }
        }
        return maxLvl;
    }
}