[Binary Tree - BFS, Medium] Maximum Level Sum of a Binary Tree

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

레벨 별 합계를 구해서, 레벨 별 합계가 가장 높은 레벨을 리턴하는 문제다.
다만 합계가 같은 경우 낮은 레벨이 우선한다.

Map을 써서 <Level, LevelSum> 으로 저장하고 max값과 일치하면 바로 리턴시키는게 아이디어였다.
BFS라서 어차피 레벨 별로 순회하기 때문에 입력순서 보장하기 위해 LinkedListMap를 사용해서 순회하다가 max == levelSum인 순간 리턴하도록 했다.

근데 생각해보니 어차피 레벨 별 순회인데 max 갈아치울 때마다 레벨만 갱신하면 되는거 아닌가 했고.. 그게 맞다.
어차피 같은 값이면 max를 갈아치우지 않고 현재 maxLevel이 그대로 유지되기 때문이다.

리팩토링 후가 1번, 리팩토링 전이 2번이다.

(1번)

class Solution {
    public int maxLevelSum(TreeNode root) {
        int max = Integer.MIN_VALUE;
        int level = 1;
        int maxLevel = 1;

        // level, sum
        Map<Integer, Integer> map = new LinkedHashMap<>();

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

        while (!que.isEmpty()) {
            int queSize = que.size();
            int tempSum = 0;

            for (int i=0; i<queSize; i++) {
                TreeNode current = que.poll();
                tempSum += current.val;

                if (current.left != null) {
                    que.offer(current.left);
                }
                if (current.right != null) {
                    que.offer(current.right);
                }
            }
            
            if (tempSum > max) {
                max = tempSum;
                maxLevel = level;
            }
            level++;
        }

        return maxLevel;
    }
}

(2번)

class Solution {
    public int maxLevelSum(TreeNode root) {
        int level = 1;
        int max = Integer.MIN_VALUE;

        // level, sum
        Map<Integer, Integer> map = new LinkedHashMap<>();

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

        while (!que.isEmpty()) {
            int queSize = que.size();
            int tempSum = 0;

            for (int i=0; i<queSize; i++) {
                TreeNode current = que.poll();
                tempSum += current.val;

                if (current.left != null) {
                    que.offer(current.left);
                }
                if (current.right != null) {
                    que.offer(current.right);
                }
            }
            
            max = Math.max(max, tempSum);
            map.put(level, tempSum);
            level++;
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == max) {
                return entry.getKey();
            }
        }
        // never?
        return level;
    }
}