LeetCode - Easy - 637. Average of Levels in Binary Tree

古城微笑少年丶 2022-10-16 09:39 204阅读 0赞

Topic

  • Tree

Description

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

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 1 0 − 5 10^{-5} 10−5 of the actual answer will be accepted.

Example 1:

ddf0607022acc04c349f552f23662210.png

  1. Input: root = [3,9,20,null,15,7]
  2. Output: [3.00000,14.50000,11.00000]
  3. Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
  4. Hence return [3, 14.5, 11].

Example 2:

4612e9bd3973edc6a569e6a58f9f4dd4.png

  1. Input: root = [3,9,20,15,7]
  2. Output: [3.00000,14.50000,11.00000]

Constraints:

  • The number of nodes in the tree is in the range [ 1 , 1 0 4 ] [1, 10^4] [1,104].
  • − 2 31 ⩽ N o d e . v a l ⩽ 2 31 − 1 -2^{31} \leqslant Node.val \leqslant 2^{31} - 1 −231⩽Node.val⩽231−1

Analysis

方法一：BFS

方法二：DFS

Submission

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.stream.Collectors;
  6. import com.lun.util.BinaryTree.TreeNode;
  8. public class AverageOfLevelsInBinaryTree { 
  10.     // 方法一：BFS
  11.     public List<Double> averageOfLevels(TreeNode root) { 
  12.         LinkedList<TreeNode> queue = new LinkedList<>();
  14.         queue.offer(root);
  15.         List<Double> result = new ArrayList<>();
  17.         while (!queue.isEmpty()) { 
  19.             int size = queue.size(), originSize = size;
  20.             long sum = 0;
  22.             for (int i = 0; i < size; i++) { 
  23.                 TreeNode node = queue.poll();
  25.                 sum += node.val;
  27.                 if (node.left != null)
  28.                     queue.offer(node.left);
  30.                 if (node.right != null)
  31.                     queue.offer(node.right);
  33.             }
  34.             result.add(sum * 1.0 / originSize);
  35.         }
  37.         return result;
  38.     }
  40.     // 方法二：DFS
  41.     public List<Double> averageOfLevels2(TreeNode root) { 
  42.         List<long[]> levelSumAndCounts = new ArrayList<>();
  43.         averageOfLevels2(root, 0, levelSumAndCounts);
  44.         return levelSumAndCounts.stream().map(a -> a[0] * 1.0 / a[1]).collect(Collectors.toList());
  45.     }
  47.     private void averageOfLevels2(TreeNode node, int level, List<long[]> levelSumAndCounts) { 
  48.         if (node == null)
  49.             return;
  51.         if (levelSumAndCounts.size() == level) { 
  52.             levelSumAndCounts.add(new long[] { node.val, 1});
  53.         } else { 
  54.             long[] temp = levelSumAndCounts.get(level);
  55.             temp[0] += node.val;
  56.             temp[1]++;
  57.         }
  59.         averageOfLevels2(node.left, level + 1, levelSumAndCounts);
  60.         averageOfLevels2(node.right, level + 1, levelSumAndCounts);
  61.     }
  62. }

Test

  1. import static org.junit.Assert.*;
  3. import java.util.List;
  5. import org.junit.Test;
  7. import com.lun.util.BinaryTree;
  8. import com.lun.util.BinaryTree.TreeNode;
  10. public class AverageOfLevelsInBinaryTreeTest { 
  12.     private TreeNode bigRoot = BinaryTree.integers2BinaryTree(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  13.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  14.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  15.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  16.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  17.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  18.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  19.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  20.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  21.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  22.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  23.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  24.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  25.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  26.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  27.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  28.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  29.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  30.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  31.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //
  32.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2147483647,2147483647,2147483647,2147483643,2147483645,2147483646,2147483646, //
  33.             2147483624,2147483646,2147483647,2147483646,2147483647,2147483647,2147483631,2147483647,2147483647,2147483647, //
  34.             2147483647,2147483631,2147483647,2147483647,2147483647,2147483647,2147483646,2147483646,2147483614,2147483646, //
  35.             2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646, //
  36.             2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646, //
  37.             2147483647,2147483644,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647, //
  38.             2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647, //
  39.             2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644, //
  40.             2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647, //
  41.             2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483642,2147483647,2147483647, //
  42.             2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647, //
  43.             2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647, //
  44.             2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636, //
  45.             2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647, //
  46.             2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647, //
  47.             2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647, //
  48.             2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647, //
  49.             2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647, //
  50.             2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647, //
  51.             2147483647,2147483647,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //
  52.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  53.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  54.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  55.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  56.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  57.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  58.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  59.             2147483642,2147483642,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //
  60.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  61.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  62.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  63.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  64.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  65.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  66.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  67.             2147483642,2147483642,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //
  68.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  69.             2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //
  70.             2147483642,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  71.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  72.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  73.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  74.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  75.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  76.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  77.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  78.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  79.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  80.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  81.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  82.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  83.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  84.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  85.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  86.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  87.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  88.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  89.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  90.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  91.             -2147483638,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  92.             -2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  93.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483643, //
  94.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  95.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483643,-2147483642,-2147483642, //
  96.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  97.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642, //
  98.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  99.             -2147483642,-2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  100.             -2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //
  101.             -2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483598,-2147483647,-2147483647,-2147483647, //
  102.             -2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647, //
  103.             -2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645, //
  104.             -2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647, //
  105.             -2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647, //
  106.             -2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647, //
  107.             -2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647, //
  108.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //
  109.             -2147483644,-2147483647,-2147483647,-2147483644,-2147483600,-2147483646,-2147483646,-2147483646,-2147483646, //
  110.             -2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483647,-2147483647, //
  111.             -2147483525,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483647,-2147483646,-2147483647, //
  112.             -2147483336);
  114.     @Test
  115.     public void test() { 
  116.         AverageOfLevelsInBinaryTree obj = new AverageOfLevelsInBinaryTree();
  118.         double delta = 10e-5;
  119.         double[] expected = { 3.00000, 14.50000, 11.00000};
  121.         List<Double> result1 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(3, 9, 20, null, 15, 7));
  122.         List<Double> result2 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(3, 9, 20, 15, 7));
  124.         for(int i = 0; i < expected.length; i++) { 
  125.             assertEquals(expected[i], result1.get(i), delta);
  126.             assertEquals(expected[i], result2.get(i), delta);
  127.         }
  130.         List<Double> result3 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(2147483647, 2147483647, 2147483647));
  131.         double[] expected3 = { 2147483647.00000, 2147483647.00000};
  133.         for(int i = 0; i < expected3.length; i++) { 
  134.             assertEquals(expected3[i], result3.get(i), delta);
  135.         }
  137.         List<Double> result4 = obj.averageOfLevels(bigRoot);
  138.         double[] expected4 = { 0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000};
  140.         for(int i = 0; i < expected4.length; i++) { 
  141.             assertEquals(expected4[i], result4.get(i), delta);
  142.         }
  143.     }
  145.     @Test
  146.     public void test2() { 
  147.         AverageOfLevelsInBinaryTree obj = new AverageOfLevelsInBinaryTree();
  149.         double delta = 10e-5;
  150.         double[] expected = { 3.00000, 14.50000, 11.00000};
  152.         List<Double> result1 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(3, 9, 20, null, 15, 7));
  153.         List<Double> result2 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(3, 9, 20, 15, 7));
  155.         for(int i = 0; i < expected.length; i++) { 
  156.             assertEquals(expected[i], result1.get(i), delta);
  157.             assertEquals(expected[i], result2.get(i), delta);
  158.         }
  161.         List<Double> result3 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(2147483647, 2147483647, 2147483647));
  162.         double[] expected3 = { 2147483647.00000, 2147483647.00000};
  164.         for(int i = 0; i < expected3.length; i++) { 
  165.             assertEquals(expected3[i], result3.get(i), delta);
  166.         }
  168.         List<Double> result4 = obj.averageOfLevels2(bigRoot);
  169.         double[] expected4 = { 0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000};
  171.         for(int i = 0; i < expected4.length; i++) { 
  172.             assertEquals(expected4[i], result4.get(i), delta);
  173.         }
  174.     }
  175. }

发表评论

表情：
评论列表 （有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读