[LeetCode] 637. Average of Levels in Binary Tree - Java[자바]

링크

문제

이진 트리의 root가 주어졌을 때, 각 레벨에 있는 노드의 평균값을 배열의 형태로 반환합니다. 실제 답의 10^-5 이내의 답이 허용됩니다.

풀이

앞서 풀었던 문제와 같이 같은 레벨에 대한 연산이 필요하다.

BFS를 사용하면 될 것 같다. BFS를 위한 Queue와, 결과를 저장할 리스트가 필요할 것으로 생각이 든다.

class Solution {  
  
    public List<Double> averageOfLevels(TreeNode root) {  
        List<Double> result = new ArrayList<>();  
        Queue<TreeNode> queue = new LinkedList<>();  
  
        queue.add(root);  
        while (!queue.isEmpty()) {  
            int size = queue.size();  
            double sum = 0;  
            for (int i = 0; i < size; i++) {  
                var node = queue.poll();  
                sum += node.val;  
                if (node.left != null) {  
                    queue.add(node.left);  
                }  
                if (node.right != null) {  
                    queue.add(node.right);  
                }  
            }  
            result.add(sum / size);  
        }  
        return result;  
    }  
}

앞선 문제와 상당히 유사해서 설명은 앞선 문제 링크를 확인하면 될 것 같다.