[Leetcode Top Interview 150] 637. Average of Levels in Binary Tree

난이도 : easy

문제링크

• binary tree의 root 노드가 주어짐
• 각 레벨의 평균값에 대한 list를 리턴하라
• 1 <= node의 갯수 <= 10000
• -2^31 <= node.val <= 2^31

 

1. 접근법

• BFS 순회방식으로 각 레벨을 순회함
• 각 레벨을 모두 순회하였을 때, list에 값을 추가한다

 

2. 의사코드

List<Double> answer = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
	TreeNode cur = null;
    double rst = 0;
    int count = 0;
    for (int i = 0; i<queue.size(); i++) {
    	cur = queue.poll();
        if (cur.left != null) queue.offer(cur.left);
        if (cur.right != null) queue.offer(cur.right);
        count += 1;
        rst+= cur.val;
    }
    
    answer.add(rst/count);
}

return answer;

 

3. 구현 코드

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

        while (!queue.isEmpty()) {
            TreeNode cur = null;
            int size = queue.size();
            double sum = 0;
            int count = 0;                                    
            
            for (int i = 0; i<size; i++) {
                cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                sum += cur.val;
                count += 1;                
            }

            answer.add(sum/count);
        }

        return answer;
    }
}

• while문을 돌 때마다 뎁스별 노드를 순회한다
  • queue size만큼 반복문을 돈다
• 뎁스별 노드의 합을 카운트와 나누어 배열에 추가한다

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(logn) - 뎁스별 변수를 선언함
                                      최악의 경우, O(n)이 될 수 있음

 

5. 개선점

• 잘 모르겠다

 

6. 회고

• 다른 풀이를 보아도 비슷하게 풀었다
• 큐를 사용하여 푸는 방법으로, BFS를 구현하는 방식이다