手撸二叉树之二叉树的层平均值

手撸二叉树之二叉树的层平均值

今天给大家带来的关于二叉树相关的算法题是二叉树的层平均值，正文如下：

题目

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例：

输入： 3 / \ 9 20 / \ 15 7输出：[3, 14.5, 11]解释：第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11]

解题思路

类似本题这种需要求解关于二叉树层次的，我们可以首先使用广度优先搜索。

从二叉树的根节点开始搜索，每一轮都遍历同一层的全部节点，计算该层的节点数以及该层节点之之和，然后再计算平均值。

说到广度优先搜索，就必须要用到队列这种数据结构来存储节点，确保每一轮遍历的时候，存储的都是同一层的节点；因为题目需要返回的是一个 List 数组，所以还需要定义一个 List 数组来存放平均值。

具体做法如下：

初始化时，将根节点加入到队列中；遍历时，先将队列中的所有节点都取出，然后将取出的每个节点值求和；判断节点对的左右节点是否有值，有值就再次将他们的左右节点加入到队列中，保证每次遍历存储的都是同一层的节点；直到队列为空，遍历终止；

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List averageOfLevels(TreeNode root) { List results = new ArrayList(); Queue queue = new LinkedList(); queue.offer(root); while (queue.size() != 0) { int size = queue.size(); Double sum = 0.0; for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); sum += node.val; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } Double average = sum / size; results.add(average); } return

最后

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。 广度优先搜索需要对每个节点访问一次，时间复杂度是 O(n)。空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。