跳至主要內容

637. 二叉树的层平均值


637. 二叉树的层平均值open in new window

🟢   🔖  深度优先搜索 广度优先搜索 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

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二叉树的层序遍历open in new window[✓] 广度优先搜索 二叉树
107二叉树的层序遍历 IIopen in new window[✓] 广度优先搜索 二叉树