리트코드 - 637. Average of Levels in Binary Tree

리트코드 - 637. Average of Levels in Binary Tree

출처 - https://leetcode.com/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 이진 트리의 루트 노드를 기반으로, 각 레벨에서 노드의 평균값을 배열 형태로 반환하세요. 실제 정답과 10^-5 이내의 오차가 있는 답변은 허용됩니다.

의사코드

list = new ArrayList q = new LinkedList q.offer(root) 반복문 시작 (q가 비어있지 않으면)     int size = q의 size     double sum = 0     반복문 시작 (1부터 size까지)         cur = q.poll()         sum +=  cur.val         if (cur의 left가 null이 아니면)             q.offer(cur의 left)         if (cur의 right가 null이 아니면)             q.offer(cur의 right)     반복문 종료     list.add(sum / size) 반복문 종료 list 리턴

 

풀이코드

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int size = q.size();
            double sum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                sum += cur.val;

                if (cur.left != null) { 
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            list.add(sum / size);
        }
        return list;
    }
}

 

코드설명

output에 보면 순서대로 결과값이 출력되어야 하므로 같은 레벨을 먼저 탐색해야 한다.

따라서 이것은 BFS가 적절하다. 문제는 "같은 레벨을 어떻게 연산하느냐?"가 핵심이다.

 

여기서 queue를 이용하는 것에 초점을 맞췄다. 먼저 q에 offer한 size를 저장해서 반복문을 돌린다.

그리고 이 size 갯수만큼만 꺼내서 아래 절차대로 확인한다.

 

1. sum에 val를 더한다.

2. left 노드가 있으면 queue에 더해준다.

3. right 노드가 있으면 queue에 더해준다.

 

이렇게 하면 아래와 같은 노드가 있다고 했을 때 같은 레벨끼리만 연산이 가능해진다.

이렇게 해서 list를 리턴하면 답이 된다.

 

그림으로 설명하면 아래와 같다.

처음 root를 queue에 넣으면 size가 1이되고, size가 1이므로 한 번만 꺼낸다.

꺼내며 node의 값을 sum에 더해주고, 자식 노드를 queue에 추가한다.

그리고 list에 sum / size 한 값을 추가한다.

이렇게 하면 list에는 레벨0의 평균값이 저장이되고(엄밀히 말하면 root는 무조건 하나이긴하지만),

queue에는 다음 레벨의 값만 저장이 되어있다.

 

queue가 비어있지 않으므로 while이 계속된다. size의 값만큼 반복문을 돌린다.

1이 poll 되며 sum에 더해지고, 자식노드가 queue에 추가된다.

마찬가지로 5가 poll 되며 sum에 더해지고, 자식노드가 queue에 추가된다.

size만큼 순회했으니 레벨 1의 값을 다 더한 sum에 size로 나눈 값을 list에 추가한다.

다음 레벨 2의 경우 자식노드가 없으므로 그냥 꺼내고 sum에만 더해준다.

sum / size 연산 후에 list에 추가되는 것은 동일하다.

 

큰 그림에서 보면 이렇게 레벨 0, 레벨 1, 레벨 2를 나누어서 연산이 가능한 것이다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

잘못된 생각1

처음에는 같은 레벨끼리만 더해야 하는데 각 자식노드끼리 더하는 합을 만들었었다.

같은 레벨끼리 더하는 방법을 더하는 값이어떤 표식을 이용하는 방법을 처음에는 생각했다가 폐기해버렸다.

 

잘못된 생각2

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int size = q.size();
            int sum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                sum += cur.val;

                if (cur.left != null) { 
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            list.add((double) sum / size);
        }
        return list;
    }
}

조건에서 int 경계값이기도 한 int의 최대값과 최소값이 기준이었다.

이렇게되면 '평균값'은 int 내에 들어와 있을지라도, sum은 int를 벗어나는 범위가 되어버린다.

int sum 부분을 double sum으로 변경하였다.

 

다른 코드

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        calculateLevels(root, levels, 0);
        
        List<Double> averages = new ArrayList<>();
        for (List<Integer> level : levels) {
            double sum = 0;
            for (int val : level) {
                sum += val;
            }
            averages.add(sum / level.size());
        }
        return averages;
    }

    private void calculateLevels(TreeNode node, List<List<Integer>> levels, int depth) {
        if (node == null) {
            return;
        }
        if (levels.size() <= depth) {
            levels.add(new ArrayList<>());
        }
        levels.get(depth).add(node.val);
        calculateLevels(node.left, levels, depth + 1);
        calculateLevels(node.right, levels, depth + 1);
    }
}

이 코드는 재귀방식으로 DFS탐색을 하고 있다.

depth를 직접 지정해서 먼저 List<List<Integer>> levels에 값을 넣고 있다.

depth가 0부터 시작하는 것과 list의 인덱스가 0부터 시작하는 것을 이용하다니 다른 문제에서 써먹어봐야겠다.

 

재귀방식임에도 런타임과 메모리는 BFS와 비슷한 편이다.

 

정리

이진트리에서 같은 레벨끼리 연산하는 두가지 방법(DFS,BFS)