637. 二叉树的层平均值（层级遍历）

637. 二叉树的层平均值（层级遍历）

• 题目
• 解题思路
• 代码

题目

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

解题思路

很容易想到要用层级遍历。关键点是要知道用queue.size()来获取该层有多少节点。然后用一个sum来保存和 ，进而求出平均值。

代码

class Solution {
    List<Double> list = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        
        /*
        因为题目说是非空，所以不用判断
        if(root==null){
            return null;
        }
        */
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            double sum = 0.00;
            int count = queue.size();//记录这一层有几个节点
            for (int i = 0; i < count; i++) {
                TreeNode cur = queue.poll();
                sum += cur.val;//求出当前层的和

                //去寻找下一层
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }

            double res = sum / count;
            list.add(res);


        }
        return list;
    }
}