637. 二叉树的层平均值
637. 二叉树的层平均值
🟢 🔖 树
深度优先搜索
广度优先搜索
二叉树
🔗 力扣
LeetCode
题目
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]
Constraints:
- The number of nodes in the tree is in the range
[1, 10^4]
. -2^31 <= Node.val <= 2^31 - 1
题目大意
按层序从上到下遍历一颗树,计算每一层的平均值。
解题思路
使用一个队列进行层序遍历,每次 for
循环时计算每层元素之和,再除以每层元素的个数 len
,即可得到平均数。
代码
/**
* @param {TreeNode} root
* @return {number[]}
*/
var averageOfLevels = function (root) {
let res = [];
if (!root) return res;
let queue = [root];
while (queue.length) {
let len = queue.length;
let temp = 0;
for (let i = 0; i < len; i++) {
if (queue[i].left) queue.push(queue[i].left);
if (queue[i].right) queue.push(queue[i].right);
temp += queue[i].val;
}
queue = queue.slice(len);
res.push(temp / len);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
102 | 二叉树的层序遍历 | [✓] | 树 广度优先搜索 二叉树 | |
107 | 二叉树的层序遍历 II | [✓] | 树 广度优先搜索 二叉树 |