题目🦀
637. 二叉树的层平均值
难度简单
给定一个非空二叉树的根节点 root
, 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5
以内的答案可以被接受。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[3.00000,14.50000,11.00000] 解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入:root = [3,9,20,15,7] 输出:[3.00000,14.50000,11.00000]
提示:
- 树中节点数量在
[1, 104]
范围内 -231 <= Node.val <= 231 - 1
解题思路🌵
- 此题采用层序遍历
- 才每一层遍历的时候记录当前的sum
- 每次层结束完成计算当前层的平均sum加入result结果集
解题步骤🌟
- 此题采用层序遍历
- 处理边界条件
- 初始化
queue
result
- 循环queue队列
- 获取queue的长度
- 遍历当前层的所有结点
- 每层循环完计算每层的平均值
- 最后返回result
源码🔥
/** * 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 result = [] const queue = [root] while(queue.length){ const len = queue.length let currentSum = 0; for(let i = 0; i < len; i++){ const node = queue.shift() currentSum += node.val node.left && queue.push(node.left) node.right && queue.push(node.right) } result.push(currentSum/len) } return result };
时间复杂度:O(N)
空间复杂度:O(N)
结束语🌞
那么鱼鱼的LeetCode算法篇的「leetCode」637-二叉树的层平均值⚡️
就结束了,虽然前端对算法要求没有后端高,但是算法是编程基础,程序=数据结构➕算法
,所以算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾
,欢迎加我好友
,一起沙雕
,一起进步
。