Viiisit [LeetCode] - 637. Average of Levels in Binary Tree

keep learning, keep coding!

Problem - Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

翻譯蒟蒻

給定一個二元樹的根節點，要求返回每一層節點值的平均值，並以一個陣列的形式呈現。對於每一層的節點，計算其值的平均數，然後將這些平均數按照層級順序存入一個陣列中。

---

• Example 1:

  Input: root = [3,9,20,null,null,15,7]
  Output: [3.00000,14.50000,11.00000]
  Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
  Hence return [3, 14.5, 11].

• Example 2:

  Input: root = [3,9,20,15,7]
  Output: [3.00000,14.50000,11.00000]

---

---

Solution - JavaScript

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 result = [];
  let queue = [root];
  while(queue.length){
    let sum = 0;
    // 記錄目前層的節點數量
    let count = queue.length; 
    for(let i = 0; i < count; i++){
      let node = queue.shift();
      sum += node.val;
      if(node.left) queue.push(node.left);
      if(node.right) queue.push(node.right);
    }
    result.push(sum / count);
  }
  return result;
};

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) {
  let sums = [], counts = [];
  function helper(node, level) {
    if (node) {
        // 如果目前層級小於 sums 的長度
        if (level < sums.length) {
            // 將節點的值加到 sums 的對應層級
            sums[level] += node.val;
            // 將 counts 的對應層級增加 1
            counts[level]++;
        } else {
            // 如果當前層級等於或大於 sums 的長度，則在 sums 和 counts 中添加新的層級
            sums.push(node.val);
            counts.push(1);
        }
        // 遞迴處理左子節點，層級加 1
        helper(node.left, level + 1);
        // 遞迴處理右子節點，層級加 1
        helper(node.right, level + 1);
    }
}
  helper(root, 0);
  return sums.map((sum, i) => sum / counts[i]);
};

Solution - Ruby

def average_of_levels(root)
  result = []
  queue = [root]
  while !queue.empty?
    sum = 0
    size = queue.size
    size.times do
      node = queue.shift
      sum += node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end
    result << sum.to_f / size
  end
  result
end

Solution - PHP

function averageOfLevels($root) {
  $result = [];
  $queue = [$root];
  while (count($queue) > 0) {
    $sum = 0;
    $count = count($queue);
    for ($i = 0; $i < $count; $i++) {
      $node = array_shift($queue);
      $sum += $node->val;
      if ($node->left) {
        array_push($queue, $node->left);
      }
      if ($node->right) {
        array_push($queue, $node->right);
      }
    }
    array_push($result, $sum / $count);
  }
  return $result;
}

LeetCode 傳送門 - Average of Levels in Binary Tree