[Leetcode][Java] 1161 Maximum Level Sum of a Binary Tree ( 이진트리의 합이 가장 큰 레벨 )

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.

 

이진트리의 루트가 주어지고, 루트의 레벨은 1이고, 루트의 자식의 레벨은 2이고 그 하위도 레벨이 1식 증가한다.

동일 레벨의 값 합이 가장 큰 레벨을 리턴하라, 단 가장 작은 레벨을 리턴하라. 

---

트리의 레벨별로 값의 합을 구하면 되므로 bfs를 이용하여 해답을 구해보자.

bfs는 Queue 자료구조를 사용하여 구현가능하다.

    public int maxLevelSum(TreeNode root) {
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int level = 0;
        int minLevel = 0, maxSum = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);

            }
            if (levelSum > maxSum) {
                maxSum = levelSum;
                minLevel = level;
            }
        }
        return minLevel;
    }

 

문제 출처 : 

leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

Maximum Level Sum of a Binary Tree - LeetCode