文档章节

637. Average of Levels in Binary Tree - LeetCode

yysue
 yysue
发布于 06/23 20:41
字数 330
阅读 22
收藏 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
粉丝 25
博文 252
码字总数 148462
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

分布式锁的那点事

在多线程并发的情况下,要保证一个代码块在同一时间只能由一个线程访问,可以用锁来保证,比如java的synchronized语法以及ReentrantLock类等等。这样子可以保证JVM进程内的多个线程同步执行。...

无语年华
2分钟前
0
0
apahce启用http2

需要前置条件传送门 其实前置做完了,h2是很简单的事 1.apache启用http2_module 2.打开apche的配置文件,写上 Protocols h2 http/1.1 3.重启apache,打开浏览器看看吧...

gcudwork
17分钟前
0
0
redis-string

set key value 设置值 set命令有以下选项: ex senconds :为健设置秒级过期时间 px millisencondes :为健设置毫秒级过期时间 nx :健不存在时候,可以设置成功,用于添加 xx : 与nx相反,不...

拐美人
23分钟前
1
0
正弦 余弦 角度 用于画时钟

<html> <head> <title>时钟</title> </head> <style> #canvas{ background: #1977ca } </style>......

一箭落旄头
40分钟前
4
0
驰狼课堂

http://www.chilangedu.com/

求是科技
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部