[Leetcode] 637. Average of Levels in Binary Tree - JS

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

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 각 레벨의 평균값을 배열로 반환하라.

제한조건
--------------------
- 노드의 갯수는 1 ~ 10^4개이다.
- -2^31 <= Node.val <= 2^31 - 1

 

2. 접근 방법

접근방법
--------------------
BFS로 순회하면서 queue 자료구조에 노드를 담는다.
BFS로 순회 시 다음 레벨의 자식 노드를 순서대로 담으므로 
자식 노드의 갯수만큼 반복문을 실행해줘서 노드의 값을 total 변수에 추가한다.
반복문 종료시 total 변수를 반복한 횟수만큼 나눠서 평균값을 구하여 결과배열에 추가한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
    const avg = [];
    const queue = [root];

    while (queue.length) {
        let levelSize = queue.length;
        let total = 0;
        
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            total += node.val;

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        avg.push(total / levelSize);
    }
    return avg
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

BFS(깊이 우선 탐색)하여 왼쪽 자식부터 우선적으로 queue 자료구조에 추가하고 자식 노드 갯수만큼 반복문을 실행해주어 해당 레벨의 노드들의 총합을 저장한다.

레벨별 반복문이 종료되면 총합을 자식 노드 갯수인 반복 횟수만큼 나눠서 평균값을 구한 뒤 이를 결과 배열에 추가한다.