leetcode637. 二叉树的层平均值，广度优先搜索BFS

leetcode637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

给定一个非空二叉树的根节点 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]

题目分析

• 问题定义：计算二叉树每层节点的平均值。
• 数据结构：使用二叉树的数据结构，其中TreeNode是一个节点，包含值val和指向左右子节点的指针。

算法介绍

• 广度优先搜索（BFS）：使用队列来实现广度优先搜索，以层序遍历树中的每个节点。

算法步骤

1. 初始化一个空向量averages来存储每层的平均值。
2. 初始化一个队列q，并将根节点root放入队列中。
3. 当队列不为空时，进行以下操作：
   • 重置当前层的总和sum为0。
   • 记录当前队列的大小size，这代表当前层的节点数。
   • 遍历当前层的每个节点：
     • 从队列中取出一个节点，将其值加到sum上。
     • 如果该节点有左子节点，将其加入队列。
     • 如果该节点有右子节点，将其加入队列。
   • 计算当前层的平均值sum/size，并将其添加到averages向量中。
4. 返回averages向量。

算法流程

算法分析

• 时间复杂度：O(n)，其中n是树中节点的数量。每个节点都被访问一次。
• 空间复杂度：O(m)，其中m是树中最大层的节点数。队列中最多可能包含该层的所有节点。
• 易错点：正确处理每一层的节点数量和总和的计算。

相似题目

题目	链接
637. 二叉树的层平均值	LeetCode
102. 二叉树的层序遍历	LeetCode
429. N叉树的层序遍历	LeetCode