637. Average of Levels in Binary Tree

---

문제 분석

이진 트리의 루트가 주어지면 각 수준의 노드 평균값을 배열 형식으로 반환합니다.

---

풀이 과정

여기서 말하는 수준은 level 이다.
같은 계층의 값들의 평균을 구하는 문제.

아래와 같은 트리가 있다고 가정한다.
input = [15, 7, 40, 1, 10, 34, 49, null, null, 8, 13]

level = 1   15 의 평균값은?
level = 2   7 + 40 의 평균값은?
level = 3   1 + 10 + 34 + 49 의 평균값은?
level = 4   8 + 13 의 평균값은?

위의 특성을 이용하여 문제를 풀려면 Queue 자료 구조 필요하다. (선입선출)
Queue 에 같은 level 의 node 를 모두 추가한다.
Queue 마지막에 추가된 node 가 우측에서 볼 수 있는 node 가 된다.
Queue 에서 node 의 left, right 노드들은 다음 level 의 node 가 된다.

1. 15 를 Queue 에 추가한다. (level = 1)
2. 현재 Queue 에 추가된 값들을 모두 꺼내 합산 후 평균값을 구한다. (level = 1)
3. 15 의 자식 노드인 7, 40 을 Queue 에 추가한다.
4. 현재 Queue 에 추가된 값들을 모두 꺼내 합산 후 평균값을 구한다. (level = 2)
5. 7, 40 의 자식 노드인 1, 10, 34, 49 를 Queue 에 추가한다.
6. 현재 Queue 에 추가된 값들을 모두 꺼내 합산 후 평균값을 구한다. (level = 3)
7. 1, 10, 34, 49 의 자식 노드인 8, 13 을 Queue 에 추가한다.
8. 현재 Queue 에 추가된 값들을 모두 꺼내 합산 후 평균값을 구한다. (level = 4)

(엄연히 따지면 자식 노드는 아니다. 다음 레벨 정도로 이해하자.)
Queue 에서 값을 꺼내 계산할 땐 size() 만큼의 반복문으로 로직을 수행한다.

---

나의 생각

---

코드

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int loopSize = queue.size();
            double sum = 0.0;

            for (int i = 0; i < loopSize; i++) {
                TreeNode node = queue.poll();
                sum += node.val;

                TreeNode left = node.left;
                TreeNode right = node.right;
                
                if(left != null) queue.offer(left);
                if(right != null) queue.offer(right);
            }

            double cal = sum / loopSize;
            result.add(cal);
        }

        return result;
    }
}