Question

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
    
      averageOfLevels(TreeNode root) {                Map
     
       store = new HashMap<>();        init(root, store, 1);        Double[] arr = new Double[store.size()];        for (Map.Entry
      
        entry : store.entrySet()) {            arr[entry.getKey() - 1] = entry.getValue().getAverage();        }        return Arrays.asList(arr);    }        void init(TreeNode root, Map
       
         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;        }    }}