[Binary Tree BFS (Breadth-First Search)] Average of Levels in Binary Tree

637. Average of Levels in Binary Tree

지문은 링크에서 확인해주세요.

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) {
  const levels = [];
  const queue = [];

  queue.push(root);

  while(queue.length) {
    const level = [];

    for(let i = queue.length - 1; i >= 0; i--) {
      const node = queue.shift();
      level.push(node.val);

      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }

    levels.push(level);
  }

  const ans = [];  

  for(const level of levels) {
    const sum = level.reduce((acc, each) => acc + each);
    ans.push(sum / level.length);
  }

  return ans;
};

연관된 직전 게시글 [Binary Tree BFS (Breadth-First Search)] Binary Tree Right Side View의 해답을 활용하였습니다.

단, 본 해답에는 의문점이 남아있습니다. for문의 조건을 역순이 아닌 순서대로 하면 같은 level 간에 집계가 되지 않습니다. 순회 횟수에도 차이가 없습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using bfs mush simple

해답의 전문은 링크를 확인해주세요.

var averageOfLevels = function(root) {
    if(!root) return 
  let queue = [root] 
  const result = []

  while( queue.length > 0) {
    const levelSize = queue.length
    let levelSum = 0

    // add up all the values on a particular level of the tree 
    for( let i = 0; i < levelSize; i++ ) {
      let atNode = queue.shift()
      levelSum += atNode.val
      if( atNode.left )  queue.push( atNode.left ) // put left side in queue (enqueue)
      if( atNode.right ) queue.push( atNode.right ) // put right side in queue (enqueue)
    }

    const levelAvg = levelSum / levelSize
    result.push(levelAvg)
  }

  return result 
};

필자의 해답과 달리, 본 해답은 순회 도중에 평균값을 도출합니다.