637. Average of Levels in Binary Tree

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<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;

        }

    }

}

巴特西

637. Average of Levels in Binary Tree - LeetCode

Question

Solution

最新文章

热门文章