[LeetCode：Average of Levels in Binary Tree] | 刷题打卡

题目描述

给你一个二叉树，以数组的形式返回每一层节点的平均数

例一：

输入: root = [3,9,20,null,15,7]
输出: [3.00000,14.50000,11.00000]
解释: 第 0 层的平均值是 3，第一层的平均值是 (9+20)/2 = 14.5, 第二层的平均值是 (15+7)/2 = 11，所以，需要返回 [3, 14.5, 11]

例二：

输入: root = [3,9,20,15,7]
输出: [3.00000,14.50000,11.00000]

思路分析

解题前需要搞清楚的几个问题：

1. 二叉树的遍历
2. 如何知道当前遍历的节点在哪一层
3. 如何计算平均值

问题一：二叉树的遍历？

二叉树的遍历不用多说，先序/中序/后序相信各位肯定能三下五除二的给怼出来，树节点的定义和先序遍历的 js 代码如下：

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}
const preOrder = (node) => {
  if (node) {
    // 访问当前节点 node：node.val;
    // 访问左子树
    preOrder(node.left);
    // 访问右子树
    preOrder(node.right);
  }
};

问题二：如何知道当前遍历的节点在哪一层？

应该也不难，给 preOrder 函数加一个 depth 参数，初始化的时候就是 preOrder(root,1)，表示根节点在第一层。递归访问左右子树时分别将 depth+1，下次递归时就能判断字数在哪一层

问题三：如何计算平均值？

暂时没想到如何在递归过程中直接得到某一层平均值，但是得到某一层节点值之和和节点个数还是可以做到的！

先定义一个如下的数组保存中间状态

const result = [
  [sum, num],
  [sum, num],
];

result[k] 表示第 k+1 层的信息，其中信息包括如下两部分：

• result[k][0]：表示第 k+1 层所有节点值之和
• result[k][1]：表示第 k+1 层节点的个数

根据问题二，可以知道递归时节点所在的层级，更新数组中相应索引值的内容即可：累加节点值，累加节点个数。

遍历结束后对 result 进行 map 处理，用节点值之和除以节点的个数，就能得到最终的结果。

AC 代码

var averageOfLevels = function (root) {
  const result = [];
  const preOrder = (node, depth) => {
    if (node) {
      if (result[depth] !== undefined) {
        result[depth][0] += node.val;
        result[depth][1]++;
      } else {
        result[depth] = [node.val, 1];
      }
      preOrder(node.left, depth + 1);
      preOrder(node.right, depth + 1);
    }
  };
  preOrder(root, 0);
  return result.map(([sum, num]) => sum / num);
};

总结

二叉树相关的问题核心就是遍历，在遍历的基础上做一些处理，最终就能达到目标结果。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情