问题

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

示例 1：

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

解法一：自解（广度优先遍历）

  1. class Solution {
  2.     public List<Double> averageOfLevels(TreeNode root) {
  3.         List<Double> res = new ArrayList<Double>();
  4.         if(root == null){
  5.             return res;
  6.         }
  8.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  9.         queue.offer(root);
  10.         while(!queue.isEmpty()){
  11.             int size = queue.size();
  12.             double sum = 0;
  13.             for(int i = 0; i < size; i++) {
  14.                 TreeNode node = queue.poll();
  15.                 sum += node.val;
  16.                 if (node.left != null) {
  17.                     queue.offer(node.left);
  19.                 }
  20.                 if (node.right != null) {
  21.                     queue.offer(node.right);
  22.                 }
  23.             }
  24.             res.add(sum/size);
  25.         }
  26.         return res;
  27.     }
  28. }
  • 时间复杂度：leetcode-637：二叉树的层平均值 - 图1，其中 n 是二叉树中的节点个数。广度优先搜索需要对每个节点访问一次，时间复杂度是 leetcode-637：二叉树的层平均值 - 图2，需要对二叉树的每一层计算平均值，时间复杂度是 leetcode-637：二叉树的层平均值 - 图3，其中 h 是二叉树的高度，任何情况下都满足 leetcode-637：二叉树的层平均值 - 图4
  • 空间复杂度：leetcode-637：二叉树的层平均值 - 图5，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n

解法二：深度优先遍历

使用深度优先搜索计算二叉树的层平均值，需要维护两个数组，counts 用于存储二叉树的每一层的节点数，sums 用于存储二叉树的每一层的节点值之和。搜索过程中需要记录当前节点所在层，如果访问到的节点在第 i 层，则将 counts[i] 的值加 1，并将该节点的值加到 sums[i]
遍历结束之后，第 i 层的平均值即为 sums[i]/counts[i]

  1. class Solution {
  2.     public List<Double> averageOfLevels(TreeNode root) {
  3.         List<Integer> counts = new ArrayList<Integer>();
  4.         List<Double> sums = new ArrayList<Double>();
  6.         dfs(root, 0, counts, sums);
  7.         List<Double> averages = new ArrayList<Double>();
  8.         int size = sums.size();
  9.         for (int i = 0; i < size; i++) {
  10.             averages.add(sums.get(i) / counts.get(i));
  11.         }
  12.         return averages;
  13.     }
  15.     public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
  16.         if (root == null) {
  17.             return;
  18.         }
  19.         if (level < sums.size()) {
  20.             sums.set(level, sums.get(level) + root.val);
  21.             counts.set(level, counts.get(level) + 1);
  22.         } else {
  23.             sums.add(1.0 * root.val);
  24.             counts.add(1);
  25.         }
  26.         dfs(root.left, level + 1, counts, sums);
  27.         dfs(root.right, level + 1, counts, sums);
  28.     }
  29. }