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 $10^{?5}$ of the actual answer will be accepted.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range $[1,10^4]$.
• $?2^{31}?Node.val?2^{31}?1$

Analysis

方法一：BFS

方法二：DFS

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;import com.lun.util.BinaryTree.TreeNode;public class AverageOfLevelsInBinaryTree {// 方法一：BFSpublic List<Double> averageOfLevels(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);List<Double> result = new ArrayList<>();while (!queue.isEmpty()) {int size = queue.size(), originSize = size;long sum = 0;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null)queue.offer(node.left);if (node.right != null)queue.offer(node.right);}result.add(sum * 1.0 / originSize);}return result;}// 方法二：DFSpublic List<Double> averageOfLevels2(TreeNode root) {List<long[]> levelSumAndCounts = new ArrayList<>();averageOfLevels2(root, 0, levelSumAndCounts);return levelSumAndCounts.stream().map(a -> a[0] * 1.0 / a[1]).collect(Collectors.toList());}private void averageOfLevels2(TreeNode node, int level, List<long[]> levelSumAndCounts) {if (node == null)return;if (levelSumAndCounts.size() == level) {levelSumAndCounts.add(new long[] {node.val, 1});} else {long[] temp = levelSumAndCounts.get(level);temp[0] += node.val;temp[1]++;}averageOfLevels2(node.left, level + 1, levelSumAndCounts);averageOfLevels2(node.right, level + 1, levelSumAndCounts);}
}

Test

import static org.junit.Assert.*;import java.util.List;import org.junit.Test;import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;public class AverageOfLevelsInBinaryTreeTest {private TreeNode bigRoot = BinaryTree.integers2BinaryTree(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, //0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2147483647,2147483647,2147483647,2147483643,2147483645,2147483646,2147483646, //2147483624,2147483646,2147483647,2147483646,2147483647,2147483647,2147483631,2147483647,2147483647,2147483647, //2147483647,2147483631,2147483647,2147483647,2147483647,2147483647,2147483646,2147483646,2147483614,2147483646, //2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646, //2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646,2147483647,2147483646, //2147483647,2147483644,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647, //2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647, //2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644, //2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483644,2147483647, //2147483647,2147483644,2147483647,2147483647,2147483644,2147483647,2147483647,2147483642,2147483647,2147483647, //2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647, //2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647, //2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636, //2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647, //2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647, //2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647, //2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647, //2147483647,2147483636,2147483647,2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647, //2147483647,2147483647,2147483647,2147483647,2147483647,2147483636,2147483647,2147483647,2147483647,2147483647, //2147483647,2147483647,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483647,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642,2147483642, //2147483642,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483638,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483643, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483643,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642,-2147483642, //-2147483643,-2147483642,-2147483642,-2147483642,-2147483642,-2147483598,-2147483647,-2147483647,-2147483647, //-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647, //-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645, //-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647, //-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647, //-2147483647,-2147483645,-2147483647,-2147483647,-2147483647,-2147483645,-2147483647,-2147483647,-2147483647, //-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647, //-2147483644,-2147483647,-2147483647,-2147483644,-2147483600,-2147483646,-2147483646,-2147483646,-2147483646, //-2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483646,-2147483647,-2147483647, //-2147483525,-2147483647,-2147483647,-2147483644,-2147483647,-2147483647,-2147483647,-2147483646,-2147483647, //-2147483336);@Testpublic void test() {AverageOfLevelsInBinaryTree obj = new AverageOfLevelsInBinaryTree();double delta = 10e-5;double[] expected = {3.00000, 14.50000, 11.00000};List<Double> result1 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(3, 9, 20, null, 15, 7));List<Double> result2 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(3, 9, 20, 15, 7));for(int i = 0; i < expected.length; i++) {assertEquals(expected[i], result1.get(i), delta);assertEquals(expected[i], result2.get(i), delta);}List<Double> result3 = obj.averageOfLevels(BinaryTree.integers2BinaryTree(2147483647, 2147483647, 2147483647));double[] expected3 = {2147483647.00000, 2147483647.00000};for(int i = 0; i < expected3.length; i++) {assertEquals(expected3[i], result3.get(i), delta);}List<Double> result4 = obj.averageOfLevels(bigRoot);double[] expected4 = {0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000};for(int i = 0; i < expected4.length; i++) {assertEquals(expected4[i], result4.get(i), delta);}}@Testpublic void test2() {AverageOfLevelsInBinaryTree obj = new AverageOfLevelsInBinaryTree();double delta = 10e-5;double[] expected = {3.00000, 14.50000, 11.00000};List<Double> result1 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(3, 9, 20, null, 15, 7));List<Double> result2 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(3, 9, 20, 15, 7));for(int i = 0; i < expected.length; i++) {assertEquals(expected[i], result1.get(i), delta);assertEquals(expected[i], result2.get(i), delta);}List<Double> result3 = obj.averageOfLevels2(BinaryTree.integers2BinaryTree(2147483647, 2147483647, 2147483647));double[] expected3 = {2147483647.00000, 2147483647.00000};for(int i = 0; i < expected3.length; i++) {assertEquals(expected3[i], result3.get(i), delta);}List<Double> result4 = obj.averageOfLevels2(bigRoot);double[] expected4 = {0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000,0.00000};for(int i = 0; i < expected4.length; i++) {assertEquals(expected4[i], result4.get(i), delta);}}
}