[Binary Tree BFS] Average of Levels in Binary Tree

1. 문제

LeetCode - Average of Levels in Binary Tree

• 이진 트리의 루트 노드가 주어졌을 때
• 각 레벨마다 노드 값의 평균을 List에 담아서 반환하는 문제

2. 접근법

• 각 레벨마다 노드 값의 평균을 구해야하기 때문에 너비 우선 탐색(BFS) 방식을 적용하기로 결정
• BFS는 Queue 자료구조를 활용하여 구현할 수 있다.
• sum에 각 레벨 노드 값을 모두 더해준 뒤, 각 레벨 노드 개수(n)로 나누어서 평균을 구한다.
• 구한 평균을 result에 담아서 반환 -> 테스트 통과!

3. 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        // 1. 각 레벨 노드 값의 평균을 담아줄 result 선언 및 초기화
        List<Double> result = new ArrayList<>();

        // 2. 너비 우선 탐색(BFS)을 하기 위해 Queue 자료구조 활용
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        // 3. queue가 빌 때까지(트리를 다 순회할 때까지) 반복
        while (!queue.isEmpty()) {
            // 각 레벨의 평균을 구하기 위해 변수 2개 선언 및 초기화
            double sum = 0L; // 각 레벨 노드들의 값의 합을 담아줄 sum
            int n = queue.size(); // 각 레벨 노드들의 개수 n

            // 각 레벨의 노드 개수만큼 반복
            for (int i = 0; i < n; i++) {
                TreeNode current = queue.poll();
                sum += current.val; // 현재 레벨의 노드 값들을 모두 더해준다
                // 자식 노드들이 있다면 queue에 추가
                if (current.left != null) queue.add(current.left);
                if (current.right != null) queue.add(current.right);
            }

            // result에 평균 값을 담아준다.
            result.add(sum / n);
        }

        // 4. 각 레벨의 평균을 담은 List result 반환
        return result;
    }
}

4. 성능

- Runtime : 2ms

- Memory : 44.3mb