[Java] 637. Average of Levels in Binary Tree

문제 파악

각 level(depth)의 노드들의 val 값 평균을 구해서 반환해야한다.

 

---

풀이

1️⃣ 그래프 탐색을 이용한 풀이 (전위 탐색)

💡 떠오른 Idea

전위 탐색을 depth를 1씩 증가시키면서 탐색을 한다.

각 depth에 도달했을 때, 해당 depth의 합과 개수를 저장하는 List를 통해 정보를 갱신한다.

탐색이 끝나고 나서, 평균 값을 구해서 반환해준다.

 

import java.util.*;
class Solution {
    List<Info> list = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();

        preOrder(root, 0);
        for (int i = 0; i < list.size(); i++) {
            Info info = list.get(i);
            ans.add(info.sum / info.cnt);
        }
        return ans;
    }

    private void preOrder(TreeNode node, int depth) {
        if (node == null) {
            return;
        }

        if (list.size() <= depth) {
            list.add(new Info(1, (double) node.val));
        } else {
            Info info = list.get(depth);
            info.cnt++;
            info.sum += node.val;
        }
        preOrder(node.right, depth + 1);
        preOrder(node.left, depth + 1);

    }
    
    static class Info{
        int cnt;
        double sum;

        public Info(int cnt, double sum) {
            this.cnt = cnt;
            this.sum = sum;
        }
    }
}

 

결과

 

2️⃣ bfs를 이용한 방법

💡 떠오른 Idea

depth 별로 합을 구하고 카운팅을 한 뒤, depth 가 달라지는 시점에 평균 값을 구하는 방식도 사용할 수 있겠다 싶었다.

따라서, 넓이 우선 탐색 방식인 bfs 방식으로 구현해보았다.

 

class Solution {
    Queue<Info> q = new LinkedList<>();
    List<Double> ans = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {

        if (root != null) {
            q.offer(new Info(root, 0));
        }

        int prevDepth = 0;
        double sum = 0;
        int cnt = 0;

        while (!q.isEmpty()) {
            Info info = q.poll();
            TreeNode node = info.node;
            int depth = info.depth;

            if (depth == prevDepth) {
                sum += node.val;
                cnt++;
            } else {
                ans.add(sum / cnt);
                prevDepth = depth;
                sum = node.val;
                cnt = 1;
            }
            if (node.left != null) {
                q.offer(new Info(node.left, depth + 1));
            }
            if (node.right != null) {
                q.offer(new Info(node.right, depth + 1));
            }
        }

        ans.add(sum / cnt);


        return ans;
    }

    static class Info {
        TreeNode node;
        int depth;

        public Info(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}

 

결과

트리를 탐색하는 방식보다는 시간이 조금더 소요되었다.

 

---

📖 회고

트리를 순회하는 방식으로도 구현해보고 큐를 이용한 bfs 방식으로도 문제를 해결해보았다.

 

여러가지 접근으로 풀어보니 트리의 구조에 대해 더 자세하게 알게 된 것 같다.