637. 二叉树的层平均值


637. 二叉树的层平均值

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

示例 1:
输入:
    3
   /
  9  20
    /  
   15   7
输出:[3, 14.5, 11]
解释:
第 0 层的平均值是 3 ,   第 1 层是 14.5 , 第 2 层是 11 。因此返回 [3, 14.5, 11] 。

深度优先搜索

/**
 * 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) &#123;
        List<Integer> counts = new ArrayList<Integer>();
        List<Double> sums = new ArrayList<Double>();
        dfs(root, 0, counts, sums);
        List<Double> averages = new ArrayList<Double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) &#123;
            averages.add(sums.get(i) / counts.get(i));
        &#125;
        return averages;
    &#125;

    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) &#123;
        if (root == null) &#123;
            return;
        &#125;
        if (level < sums.size()) &#123;
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        &#125; else &#123;
            sums.add(1.0 * root.val);//每层进来都走else,右节点dfs时执行if分支。
            counts.add(1);
        &#125;
        dfs(root.left, level + 1, counts, sums); //else
        dfs(root.right, level + 1, counts, sums);//if分支
    &#125;
// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/
&#125;

广度优先搜索

public List<Double> averageOfLevels(TreeNode root) &#123;
        List<Double> averages = new ArrayList<Double>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) &#123;
            double sum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) &#123;
                TreeNode node = queue.poll();
                sum += node.val;
                TreeNode left = node.left, right = node.right;
                if (left != null) &#123;
                    queue.offer(left);
                &#125;
                if (right != null) &#123;
                    queue.offer(right);
                &#125;
            &#125;
            averages.add(sum / size);
        &#125;
        return averages;
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
1299. 将每个元素替换为右侧最大元素 1299. 将每个元素替换为右侧最大元素
1299. 将每个元素替换为右侧最大元素给你一个数组  arr ,请你将每个元素用它右边最大的元素替换,如果是最后一个元素,用  -1 替换。完成所有替换操作后,请你返回这个数组。示例 1:输入:arr = [17,18,5,4,6,1]输
2021-02-28 future
下一篇 
剑指 Offer 18. 删除链表的节点 剑指 Offer 18. 删除链表的节点
剑指 Offer 18. 删除链表的节点给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 注意:此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5输出:
2021-02-28 future
  目录