637. Average of Levels in Binary Tree - LeetCode
发布时间:2020-12-14 03:23:37 所属栏目:大数据 来源:网络整理
导读:Question 637.?Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每层的平均数放到数组里,最后数组转为list返回,不用考虑list里的排序
Question637.?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,level+1); init(root.right,level+1); } // 定义一个类存储每一层的信息 class TreeLevel { int count; // 该层有多少元素 double sum; // 该层所有元素的和,这个要用double类型来保存,eg:[2147483647,2147483647,2147483647] // 返回该层的平均数 Double getAverage() { return sum / count; } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |