[LeetCode] Average of Levels in Binary Tree - Javascript

Average of Levels in Binary Tree

[이진트리의 각 레벨에서의 평균 값 구하기]

 

제약 조건 

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Example

 

문제 접근 방식

이전에 풀었던 방식처럼 재귀를 이용해서 풀면 될 것 같았다.

재귀 함수 내에서는 sms[level]에 값을 넣을 때 data.val의 합계를 넣는다

즉 각 레벨에서의 노드의 합계를 모두 더해 배열에 넣는다.

위의 사진을 예시로 했을 때, sum[3,29,22]가 들어가게 된다.
sum 배열의 0부터 2까지의 레벨은 각각 트리의 레벨을 의미한다.

cnt 배열에는 각 레벨의 노드의 개수가 들어간다.
예시로 들자면 cnt[1,2,2]가 들어가게 된다. 

 

해당 연산을 하는 이유는 평균값을 구해야 하기에 노드의 개수를 저장하는 것이다.
재귀 호출이 모두 끝난 후 마지막으로 aver 배열에 합계를 구한
sum 배열과 노드의 개수가 들어간 cnt 변수를 나누기해 각 트리의 레벨의 평균값을 구한다.

 

solve 코드

/**
 * 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 cnt = [];
    const sums = [];
    const aver = [];
    const recursive = (data, level) => {
        if (!data){
            return null
        } 
        if (sums[level] == undefined) {
            sums[level] = 0
            cnt[level] = 0
        }
        sums[level] += data.val
        cnt[level] += 1

        recursive(data.left, level + 1)
        recursive(data.right, level + 1)
    }

    recursive(root, 0)

    for (let i=0; i<cnt.length; i++) {
        aver.push(sums[i]/cnt[i])
    }

    return aver;
};