637. Average of Levels in Binary Tree

문제 링크: https://leetcode.com/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150

문제

주어진 이진 트리의 각 레벨에 있는 노드의 평균 값을 배열의 형태로 반환하자.

• 이진 트리의 root

출력

• 정수 배열

---

나의 풀이

접근

같은 레벨에 있는 노드의 평균을 구하는 문제이기 때문에, DFS보단 BFS 방식이 맞을 거라 생각했고, 앞서 푼 문제에서 이용한 Queue 를 이용해보기로 했다.

구현 코드

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

        while (!queue.isEmpty()) {
            int size = queue.size();

            while(size-- > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (size == 0) {
                    Long sum = list.stream().mapToLong(Long::valueOf).sum();
                    int divider = (list.size() != 0) ? list.size() : 1;     
                    res.add(sum / (double) divider);
                    list.clear();
                }

                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        return res;

    }
}

• queue에 root부터 넣으며 BFS를 시작한다.
• 임시 list를 생성해 같은 레벨에 있는 노드 값을 삽입
• 만약 같은 레벨에 있는 노드를 다 탐색하면, 임시 list에 있는 값의 합계와 개수를 통해 같은 레벨의 노드들의 평군을 구한 후, 임시 list를 clear 시킨다.

결과

Time: O(n)

같은 레벨에 있는 노드의 평균을 계산할 때, list.stream().mapToLong(Long::valueOf).sum(); O(같은 레벨의 노드 수) 만큼의 시간복잡도를 가지고, BFS는 트리의 모든 노드를 탐색하기 때문에 BFS 알고리즘은 O(N)의 시간복잡도를 가진다.

Space: O(n)

---

다른 풀이

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    
    if(root == null) return result;
    q.add(root);
    while(!q.isEmpty()) {
        int n = q.size();
        double sum = 0.0;
        for(int i = 0; i < n; i++) {
            TreeNode node = q.poll();
            sum += node.val;
            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);
        }
        result.add(sum / n);
    }
    return result;
}

이 코드는 불필요하게 따로 list를 생성해 값을 저장하지 않고, sum 이라는 변수를 두어, 바로 합계를 계산했다.

따라서, 합계를 구하는 시간이 감소되어 좀 더 빠른 코드를 구현할 수 있었던 것 같다.