文档章节

637. Average of Levels in Binary Tree - LeetCode

yysue
 yysue
发布于 06/23 20:41
字数 330
阅读 25
收藏 0

Question

637. Average of Levels in Binary Tree

Solution

思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每层的平均数放到数组里,最后数组转为list返回,不用考虑list里的排序了.

Java实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        
        Map<Integer, TreeLevel> store = new HashMap<>();
        init(root, store, 1);
        Double[] arr = new Double[store.size()];
        for (Map.Entry<Integer, TreeLevel> entry : store.entrySet()) {
            arr[entry.getKey() - 1] = entry.getValue().getAverage();
        }
        return Arrays.asList(arr);
    }
    
    void init(TreeNode root, Map<Integer, TreeLevel> store, int level) {
        if (root == null) return;
        TreeLevel treeLevel = store.get(level);
        if (treeLevel == null) {
            treeLevel = new TreeLevel();
            store.put(level, treeLevel);
        }
        treeLevel.count++;
        treeLevel.sum+=root.val;
        init(root.left, store, level+1);
        init(root.right, store, level+1);
    }
    
    // 定义一个类存储每一层的信息
    class TreeLevel {
        int count; // 该层有多少元素
        double sum; // 该层所有元素的和,这个要用double类型来保存,eg:[2147483647,2147483647,2147483647]
        
        // 返回该层的平均数
        Double getAverage() {
            return sum / count;
        }
    }
}

© 著作权归作者所有

共有 人打赏支持
yysue
粉丝 27
博文 268
码字总数 155357
作品 0
济南
程序员
私信 提问
Leetcode 637. Average of Levels in Binary Tree

题目链接 https://leetcode.com/problems/average-of-levels-in-binary-tree/description/ 题目描述 Given a non-empty binary tree, return the average value of the nodes on each level......

xgnming
09/06
0
0
LeetCode笔记:637. Average of Levels in Binary Tree

问题(Easy): Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Example 1: Input: Output: [3, 14.5, 11] Explanation: T......

Cloudox_
01/11
0
0
[leetcode]Binary Search Tree Iterator

question Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling will return the next smallest number in th......

NineRec
2015/08/27
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
[LeetCode] Maximum Width of Binary Tree 二叉树的最大宽度

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structu......

机器的心脏
2017/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊storm的ICommitterTridentSpout

序 本文主要研究一下storm的ICommitterTridentSpout ICommitterTridentSpout storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSpout.java public interface......

go4it
29分钟前
1
0
Ubuntu常用操作

查看端口号 netstat -anp |grep 端口号 查看已使用端口情况 netstat -nultp(此处不用加端口号) netstat -anp |grep 82查看82端口的使用情况 查找被占用的端口: netstat -tln netstat -tl...

hc321
昨天
1
0
网站cdn的静态资源突然访问变的缓慢,问题排查流程

1.首先我查看了一下是否自己的网络问题,通过对比其他资源的访问速度和下载速度,确认不是 2.通过ping 和 tracert 判断cdn域名能否正常访问,(最后回想感觉这一步可以省略,因为每次最终能访...

小海bug
昨天
3
0
Mybatis 学习笔记四 MyBatis-Plus插件

Mybatis 学习笔记四 MyBatis-Plus插件 maven依赖 <dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus</artifactId> <ve......

晨猫
昨天
5
0
小白带你认识netty(二)之netty服务端启动(下)

承接上一篇小白带你认识netty(二)之netty服务端启动(上),还剩下两步骤:3、注册Selector:将Channel注册到Selector上 和 4、端口的绑定:服务端端口的监听。 3、注册Selector:将Chann...

天空小小
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部