[자바] Leetcode 637 - Average of Levels in Binary Tree

leetcode.com/problems/average-of-levels-in-binary-tree/

Average of Levels in Binary Tree - LeetCode

기초 BFS문제인데, BFS로 풀 수 있음을 파악하는 데 오래 걸렸다. 슬프다.

 

root를 Queue<TreeNode> queue에 넣은 다음에, 하나씩 뽑으면서 left와 right 노드를 다시 queue에 넣어준다.

while문을 타면서 한 레벨의 노드개수가 변수 size에 들어갈 것이고, 그 size만큼 for문을 타면서 다시 그 노드들의 자식 노드들을 넣어준다. 이때 sum변수에 각 노드의 val도 넣어준다.

for문을 나오고 나서는 여태까지 계산된 sum을 size로 나누면 해당 레벨의 평균값을 구할 수 있게 된다. 

     3
    / \
 9    20
        / \
     15 7

문제에서 주어진 위 예시로 생각해보면, 

root인 3일 때에는 for문을 타면서 queue에 9와 20이 들어갈 것이고, 그 다음번 while을 돌 때에는 size=2가 되면서 for문을 2번 돌게 된다. 이때 9와 20은 모두 pop()되지만, 그 자식노드들이 다시 add()되고, 동시에 sum 변수에 9와 20이 더해지게 된다. 

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        
        //평균값을 담을 List변수
        List<Double> avg = new ArrayList<>();
        
        if(root==null) return avg;
        
        
        //Queue를 생성하여 root 추가
        Queue<TreeNode> que  = new LinkedList<>();
        que.add(root);
        
        TreeNode curr;
        while(!que.isEmpty()){
            int size = que.size();
            double sum = 0;
            
            //각 레벨에 존재하는 노드의 개수만큼 for문을 타면서 노드를 poll()
            for(int i=0;i<size;i++){
                curr = que.poll();
                sum += curr.val;
                
                if(curr.left!=null) que.add(curr.left);
                if(curr.right!=null) que.add(curr.right);
            }
            
            //avg에 평균값 저장 
            avg.add(sum/size);
        }
        
        
        return avg;
    }

}