637. Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

Average of Levels in Binary Tree - LeetCode

 

1. 문제풀이 아이디어

트리의 레벨이 같을 때 같은 레벨의 각 데이터들을 노드의 수로 나눈 평균을 구하고 결과를 List컬렉션에 담아서 리턴하면 해결할 수 있는 문제이다.

 

2.문제의 해결방법 표현

레벨 0을 Queue컬렉션에 담은 후에 Queue의 사이즈 만큼 순회하여 데이터를 sum 변수에 더한다.

이진 탐색트리로 왼쪽자식과 오른쪽 자식노드가 존재하기 때문에 자식이 널이아니라면 Queue컬렉션에 더한후에

각 레벨마다 저장된 sum의 결과에 해당 레벨의 노드의 수로 나누면 각 레벨의 평균을 구할 수 있다.

반복하여 results 리스트에 담아서 리턴한다.

 

3.코드구현

import java.util.*;

class Solution {

    public void bfs(List<Double> results, TreeNode root, int level, Queue<TreeNode> queue )
    {
        queue.offer(root);
        while(!queue.isEmpty())
        {
            double avg = 0;
            double sum = 0;
            int num = 0;
            int size = queue.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode cur = queue.poll();
                sum += cur.val;
                if(cur.left != null)
                    queue.offer(cur.left);
                if(cur.right != null)
                    queue.offer(cur.right);
                num = i;
                
            }
            avg = sum / (num+1);
            
            
            results.add(avg);
            
        }
    }

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> results = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        bfs(results, root, 0, queue);

        return results;
    }
}