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

HelloWorld杰少

关注

发布于: 刚刚

Hello, 大家好，今天是我参加 8 月更文的第 20 天，今天给大家带来的关于二叉树相关的算法题是二叉树的层平均值，正文如下：

题目

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

示例：

输入：    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<Double> averageOfLevels(TreeNode root) {        List<Double> results = new ArrayList();        Queue<TreeNode> 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 results;    }}

复制代码

最后

复杂度分析：

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

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/cc0ae9afe4945b2cea6b72edf】。文章转载请联系作者。

HelloWorld杰少

关注

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

发布

暂无评论

创作场景

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

题目

解题思路

代码实现

最后

HelloWorld杰少

评论