[알고리즘] LeetCode - Average of Levels in Binary Tree

Average of Levels in Binary Tree - LeetCode

문제 설명

• 이진 탐색 트리의 root 노드가 주어진다.
• 이진 탐색 트리에서 각 레벨 노드들의 평균값을 반환해야 한다.

문제 해결

• 같은 깊이(레벨)에 있는 노드끼리의 결과값을 구하는 문제이기 때문에 너비 우선 탐색이 적합하다고 생각했다.
• bfs를 통해 너비 우선 탐색으로 레벨 별 합계를 구했다.
• 레벨이 바뀌는 구간에서 평균을 구해 실수형 리스트인 answer에 저장했다.
• root 기준으로 왼쪽이나 오른쪽 자식이 있는 경우에만 Queue에 삽입하여 불필요한 연산을 최대한 줄였다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    static class Node {
        TreeNode node;
        int depth;
        public Node(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public List<Double> averageOfLevels(TreeNode root) {
        return bfs(root);
    }

    static List<Double> bfs(TreeNode root) {
        List<Double> answer = new ArrayList<>();
        
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(root, 0));

        long depth = 0, sum = 0, count = 0;
        while(!q.isEmpty()) {
            Node now = q.poll();

            sum += now.node.val;
            count++;

            if (q.isEmpty() || q.peek().depth != depth) {
                answer.add((double) sum / count);
                sum = 0;
                count = 0;
                depth++;
            }

            if (now.node.left != null) 
                q.add(new Node(now.node.left, now.depth + 1));

            if (now.node.right != null)
                q.add(new Node(now.node.right, now.depth + 1));
        }

        return answer;
    }
}

결과

시간	메모리
4 ms	44.3 MB