[Easy] LeetCode - no.637 Average of Levels in Binary Tree : Java

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

 

 

문제

이진 트리의 root가 주어졌을 때, 각 레벨별 평균을 구하여 반환할 것

 

Example 1

 

 

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

 

 

 

 

 

 

 

풀이

참고

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

    // BFS
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = 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++) {
                TreeNode node = queue.poll();
                sum += node.val;

                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            list.add(sum / size);
        }

        return list;
    }

• 레벨별 평균 계산이니 BFS 활용
• 레벨별 sum(double)과 queue.size()를 가지고 평균값 계산 후 list에 add()
• 시간복잡도 : O(N)

 

알고 나니 BFS를 활용하는게 정말 적절하다는 생각이 든다...

왜 혼자서는 떠올리지 못할까 ㅜ.ㅜ