Sponsored
Sponsored
This approach uses a Breadth-First Search (BFS) strategy to traverse the binary tree level by level. For each level, we calculate the sum of node values and the count of nodes, then compute the average for each level. The BFS technique helps in handling each level independently using a queue.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(M), where M is the maximum number of nodes at any level, corresponding to the queue holding these nodes.
In the Python implementation, BFS is achieved using a deque as a queue. As each level is processed, the sum of node values is calculated, followed by the averaging of these values. This results in averages returned for each tree level.
This approach makes use of Depth-First Search (DFS) combined with pre-order traversal. The key idea is to traverse the tree, keeping track of the sum of node values and the count of nodes at each level. Recursive traversal helps gather the necessary values efficiently for averaging.
Time Complexity: O(N), where N signifies the number of tree nodes.
Space Complexity: O(H), where H is the height of the tree due to recursion stack.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11 public List<Double> averageOfLevels(TreeNode root) {
12 List<Double> averages = new ArrayList<>();
13 List<Long> levelSums = new ArrayList<>();
14 List<Integer> levelCounts = new ArrayList<>();
15 dfs(root, 0, levelSums, levelCounts);
16 for (int i = 0; i < levelSums.size(); i++) {
17 averages.add((double) levelSums.get(i) / levelCounts.get(i));
18 }
19 return averages;
20 }
21
22 private void dfs(TreeNode node, int level, List<Long> sums, List<Integer> counts) {
23 if (node == null) return;
24 if (level == sums.size()) {
25 sums.add((long) node.val);
26 counts.add(1);
27 } else {
28 sums.set(level, sums.get(level) + node.val);
29 counts.set(level, counts.get(level) + 1);
30 }
31 dfs(node.left, level + 1, sums, counts);
32 dfs(node.right, level + 1, sums, counts);
33 }
34
35 public static void main(String[] args) {
36 TreeNode a = new TreeNode(3);
37 TreeNode b = new TreeNode(9);
38 TreeNode c = new TreeNode(20);
39 TreeNode d = new TreeNode(15);
40 TreeNode e = new TreeNode(7);
41
42 a.left = b;
43 a.right = c;
44 c.left = d;
45 c.right = e;
46
47 Solution sol = new Solution();
48 List<Double> result = sol.averageOfLevels(a);
49 result.forEach(avg -> System.out.print(avg + " "));
50 }
51}The Java solution leverages DFS to manage levels via recursion. Each node's values augment cumulative level sums and counts, facilitating average computation.