637. Average of Levels in Binary Tree

题干简述：

给我们一个二叉树的根节点，求解该二叉树每层节点的平均值。

每层节点的平均值平均值 = 每层节点和 / 每层节点数

解题思路

首先，我们可以提取出题干的关键词“每层”，这就给我们解题的思路了。二叉树，层，映入脑海的自然是 BFS 广度优先遍历了。

BFS 的实现原理很简单，通过一个数组来维护一个队列，由于队列的 FIFO（先入先出）特性，在每个节点出队的时候，我们可以将其子节点入队，这样，当这一层节点全部出队的时候，它下一层的所有节点此时都已经入队了。这一题，要求我们就算每层节点的平均值，要计算平均值，我们需要得到两个值，当前层所有节点和，与当前层所有节点数目。重点，就在于如何获取到当前层。

637-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) {
    if (!root) return [];
    const queue = [root];
    const res = [];
    while (queue.length) {
        const len = queue.length;
        let sum = 0;
        for (let i = 0;i < len;i++) {
            const node = queue.shift();
            sum += node.val;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(sum / len);
    }
    return res;
};

BFS 能解决的题目，大多也可以通过 DFS（深度优先遍历）解决，当然，会繁琐很多。DFS 解法需要维护两个数组，sums 用于维护每一层的节点和，count 用于维护每一层的节点数。相较于普通的DFS递归函数，我们这里额外需要一个参数 level，用于辅助判断当前节点属于哪一层，并借此决定操作 sums 和 count 数组中的哪一项。

题解如下：

var averageOfLevels = function(root) {
    const sums = [];
    const count = [];
    const dfs = (node, level) => {
        if (!node) return;
        const len = sums.length;
        if (level < len) {
            sums[level] += node.val;
            count[level] += 1;
        } else {
            sums[level] = node.val
            count[level] = 1;
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    const res = [];
    for (let i = 0;i < sums.length;i++) {
        res.push(sums[i] / count[i]);
    }
    return res;
};

Q.E.D.

Take it easy