广度优先遍历 BFS
解题思路
对二叉树进行层次遍历；
每一轮遍历时，将队列中的节点全部取出，计算这些节点的数量以及它们的节点值之和，并计算这些节点的平均值，放入 res 中；
重复上述操作直到队列为空，遍历结束；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树中的节点个数；- 广度优先搜索需要对每个节点访问一次，时间复杂度是
O(n)； - 需要对二叉树的每一层计算平均值，时间复杂度是
O(h)，其中 h 是二叉树的高度，任何情况下都满足h ≤ n，因此总时间复杂度是O(n)；
- 广度优先搜索需要对每个节点访问一次，时间复杂度是
-
空间复杂度：
O(n)，其中 n 是二叉树中的节点个数；空间复杂度取决于队列开销，队列中的节点个数不会超过 n；
代码实现
var averageOfLevels = function (root) {
if (root === null) return [];
let res = [];
let queue = [root]; // 声明队列用于存储后续数据
// 遍历队列
while (queue.length) {
let sum = 0; // 针对本轮操作，创建一个 sum
let len = queue.length; // 一层的数据量
for (let i = 0; i < len; i++) {
// 将本次操作的结点出队
let node = queue.shift();
sum += node.val;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
res.push(sum / len);
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 199. 二叉树的右视图
上一篇
评论
