题目地址(637. 二叉树的层平均值)

https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/

题目描述

  1. 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
  5. 示例 1：
  7. 输入：
  8.     3
  9.    / \
  10.   9  20
  11.     /  \
  12.    15   7
  13. 输出：[3, 14.5, 11]
  14. 解释：
  15. 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
  20. 提示：
  22. 节点值的范围在32位有符号整数范围内。

前置知识


公司

  • 暂无

思路

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public List<Double> averageOfLevels(TreeNode root) {
  19.             ArrayList<Double> res = new ArrayList<>();
  20.             Queue<TreeNode> queue = new LinkedList<>();
  21.             queue.offer(root);
  22.             int size = 0;
  23.             double num = 0.0;
  24.             while (!queue.isEmpty()) {
  25.                 size = queue.size();
  26.                 num = 0.0;
  27.                 for (int i = 0; i < size; i++) {
  28.                     TreeNode poll = queue.poll();
  29.                     num += poll.val;
  30.                     if (poll.left != null) {
  31.                         queue.offer(poll.left);
  32.                     }
  33.                     if (poll.right != null) {
  34.                         queue.offer(poll.right);
  35.                     }
  36.                 }
  37.                 res.add(num/size);
  38.             }
  39.             return res;
  40.         }
  41.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：637. 二叉树的层平均值 - 图1#card=math&code=O%28n%29&id=rXOnJ)
  • 空间复杂度：637. 二叉树的层平均值 - 图2#card=math&code=O%28n%29&id=Hr1tL)