文档章节

637. Average of Levels in Binary Tree - LeetCode

yysue
 yysue
发布于 06/23 20:41
字数 330
阅读 18
收藏 0
点赞 0
评论 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
粉丝 16
博文 181
码字总数 120884
作品 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
[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
[LeetCode] Binary Tree Level Order Traversal

★ 题目 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left......

u013553529
01/13
0
0
[LeetCode] Second Minimum Node In a Binary Tree

[LeetCode] Second Minimum Node In a Binary Tree 题目 https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/ Given a non-empty special binary tree consisting of node......

u013553529
2017/11/25
0
0
leetcode -- Maximum Depth of Binary Tree

Maximum Depth of Binary Tree Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest......

leiline
01/12
0
0
leetcode -- Balanced Binary Tree

Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of t......

leiline
01/12
0
0
LeetCode:Invert Binary Tree - 反转二叉树

1、题目名称 Invert Binary Tree(反转二叉树) 2、题目地址 https://leetcode.com/problems/invert-binary-tree/ 3、题目内容 英文: Invert a binary tree. to 中文:反转一颗二叉树。 4、...

北风其凉
2016/02/11
483
1
Binary Tree Traversal - two styles of solutions

经过查询资料,主要有两种风格的iterative solution for binary tree traversal For example, for the preorder traversal, there are two kinds of iterative solutions. Pay attention to ......

s360564346
2016/11/25
8
0
【刷题】Lowest Common Ancestor

最低公共祖先 Lowest Common Ancestor 三连击. basic problem lintcode戳我(有follow up) leetcode戳我 题目 Description Given the root and two nodes in a Binary Tree. Find the lowe......

猴子007
2017/12/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

使用爬虫实现代理IP池之放弃篇

啥叫代理IP以及代理IP池 概念上的东西网上搜索一下就好了,这里简单科普一下(大部分会读这篇文章的人,基本是不需要我来科普的),白话说就是能联网并提供代理访问互联网的服务器,它提供的...

一别丶经年
3分钟前
0
0
rabbitmq学习记录(五)交换机Exchange-fanout

之前学习的都是一条消息发给一个消费者,下面开始记录如何把一条信息发给多个消费者 这边我们用到了交换机Exchange 交换机模式:fanout 模式特点:生产者把消息发送给Exchange之后,Exchang...

人觉非常君
24分钟前
0
0
sqoop导入数据到Base并同步hive与impala

使用Sqoop从MySQL导入数据到Hive和HBase 及近期感悟 基础环境 Sqool和Hive、HBase简介 Sqoop Hive HBase 测试Sqoop 使用Sqoop从MySQL导入数据到Hive 使用复杂SQL 调整Hive数据类型 不断更新 ...

hblt-j
30分钟前
0
0
Dart 服务端开发 文件上传

clent端使用angular组件 upload_component.html form id="myForm" method="POST" enctype="multipart/form-data"> <input type="file" name="fileData"> <!-- file field --></form>......

scooplol
30分钟前
0
0
apache和tomcat同时开启,乱码问题

tomcat和apache同时开启,会走apache的转发,执行的是AJP/1.3协议。所以在tomcat的配置文件server中, <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" useBodyEncodingForU......

Kefy
47分钟前
0
0
使用ssh-keygen和ssh-copy-id三步实现SSH无密码登录 和ssh常用命令

ssh-keygen 产生公钥与私钥对. ssh-copy-id 将本机的公钥复制到远程机器的authorized_keys文件中,ssh-copy-id也能让你有到远程机器的home, ~./ssh , 和 ~/.ssh/authorized_keys的权利 第一步...

xtof
今天
0
0
orcale 查询表结构

SELECT t.table_name, t.colUMN_NAME, t.DATA_TYPE || '(' || t.DATA_LENGTH || ')', t1.COMMENTS FROM User_Tab_Cols t, User_Col_Comments t1WHERE t.table_name......

wertwang
今天
0
0
Java 之 反射

反射,剖析 Java类 中的 各个组成部分,映射成 一个个 Java对象,多用于 框架和组件,写出复用性高的通用程序。 测试类代码如下: class Person { private String name; public St...

绝世武神
今天
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
今天
0
0
多 SSH Key 实现同一台服务器部署多 Git 仓库

本文以以下需求为背景,介绍详细的做法: 需在同一台服务器同时部署两个不同的 Github 仓库(对 Bitbucket 等 git 服务同样适用) root 用户可在远程登录 SSH 后附上预期的 SSH Key 进行 gi...

yeahlife
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部