[LeetCode/JAVA] 637. Average of Levels in Binary Tree

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/average-of-levels-in-binary-tree/

Average of Levels in Binary Tree - LeetCode

문제 설명

출처 : LeetCode

주어진 TREE의 각 depth별 평균 값을 담은 배열(리스트)를 반환하세요

풀이방법

기본 BFS 탐색 로직을 그대로 사용하였습니다.
1. Depth별 평균 값을 구해야하기 때문에, Depth 당 값을 합산하는 sum 변수를 0으로 초기화
2. sum과 depth별 노드의 개수(size)를 나누어 평균 값을 계산
자바에서 double형과 int형을 연산하면 double형이 return 되기 때문에 불필요한 형 변환을 하지 않도록 코딩했습니다.

내 코드(JAVA)

 

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

    q.add(root);

    while (!q.isEmpty()) {

        int size = q.size();
        double sum = 0;				// depth별 합산 초기화
        for(int i=0; i<size; i++) {
            TreeNode node = q.poll();
            if(node.left != null) q.add(node.left);
            if(node.right != null) q.add(node.right);

            sum += node.val;			// 값 누적
        }
        res.add(sum/size);			// 평균 값 계산 후 추가
    }

    return res;
}