solution 1

/**
 * 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) {
    let queue = [];
    let result = [];

    queue.push(root);

    while(queue.length !== 0){
      	// 현재 Queue의 길이를 저장한다. 같은 레벨만 연산하기 위함이다.
        const sameLevelLength = queue.length;
      
      	// 같은 레벨 노드 값의 누적 합
        let sumOfSameLevel = 0;

        for(let i = 0; i < sameLevelLength; i++){
          	// Queue에서 나온 노드는 연산이 끝난 노드가 된다.
            let curr = queue.shift();

            sumOfSameLevel += curr.val;
	
          	// 연산이 끝난 노드의 왼쪽 자식 노드
            if(curr.left){
                queue.push(curr.left);
            }

            // 연산이 끝난 노드의 오른쪽 자식 노드
            if(curr.right){
                queue.push(curr.right);
            }
        }

        result.push(sumOfSameLevel / sameLevelLength);
    }

    return result;
};

BFS 문제는 Queue를 사용해서 해결한다.
따라서, 배열을 활용해서 Queue 구조를 사용했다.
여기서 중요한 것은 "같은 레벨"의 노드만 누적합 연산에 사용하는 것이다.

그런데, Queue는 계속 변할텐데...?
그렇다.
그래서 같은 레벨임을 확인하기 위해 연산 시작 전에 Queue의 길이를 저장한다.
이미 지난 노드는 Queue에서 빠져 나가기 때문에 다음 레벨을 연산할 때는 영향이 없고,
새롭게 들어온 노드가 문제인데, 들어오기 전 Queue의 길이를 저장해놓으면
새로 들어온 노드까지 연산 횟수가 도달하지 못하고 끝나기 때문에 이를 해결할 수 있다!

다만, 이 방법은 배열을 사용해서 Queue를 구현했기 때문에,
시간 복잡도가 완전히 Queue와 동일하다고 볼 수는 없다.
일반적인 배열에서는 shift()가 O(n)의 시간 복잡도를 가지기 때문이다.
Queue에서는 dequeue가 O(1)의 시간 복잡도를 가지는데도 말이다.

그래서 Linked List를 사용해서 Queue를 구현하는 것으로 문제를 해결해보았다.

solution 2

/**
 * 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) {
    class Node {
        constructor(node) {
            this.treeNode = node;
            this.next = null;
        }
    }

    class Queue {
        constructor() {
            this.first = null;
            this.last = null;
            this.size = 0;
        }

        enqueue(node) {
            let newNode = new Node(node);
    
            if (!this.first) {
              this.first = newNode;
              this.last = newNode;
            } else {
              this.last.next = newNode;
              this.last = newNode;
            }
    
            return ++this.size;
        }

        dequeue() {
            if (!this.first) {
              return null;
            }

            let temp = this.first;

            if (this.size === 1) {
              this.last = null;
            }

            this.first = this.first.next;

            temp.next = null;

            this.size--;

            return temp;
        }
    }

    let queue = new Queue();
    let result = [];

    queue.enqueue(root);

    while(queue.size !== 0){
        const sameLevelLength = queue.size;
        let sumOfSameLevel = 0;

        for(let i = 0; i < sameLevelLength; i++){
            let curr = queue.dequeue();

            sumOfSameLevel += curr.treeNode.val;

            if(curr.treeNode.left){
                queue.enqueue(curr.treeNode.left);
            }

            if(curr.treeNode.right){
                queue.enqueue(curr.treeNode.right);
            }
        }
        
        result.push(sumOfSameLevel / sameLevelLength);
    }

    return result;
};

배열을 사용했던 것을 Linked List를 통해 구현한 Queue로 변경하였다.
treeNode에 인자로 들어온 node를 담아서 사용하기 때문에 queue.treeNode를 통해 node에 접근 할 수 있다. 그 외의 로직은 전부 동일하다.
그런데...시간 복잡도가 많이 개선될 줄 알았는데 거의 동일한 수준으로 나오고 있다.
심지어 같은 로직을 사용하는 다른 분들의 풀이는 연산 시간이 더 빠르다...
로직이 동일하기 때문에 어떤 부분에서 차이가 발생하는지 알 수가 없었지만,
배열과 Linked List 모두를 사용해서 BFS 문제를 해결했다는 것에 큰 의미가 있다!