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.
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 Queue<TreeNode> queue = new LinkedList<>();
14 queue.offer(root);
15 while (!queue.isEmpty()) {
16 int count = queue.size();
17 double sum = 0;
18 for (int i = 0; i < count; i++) {
19 TreeNode node = queue.poll();
20 sum += node.val;
21 if (node.left != null) queue.offer(node.left);
22 if (node.right != null) queue.offer(node.right);
23 }
24 averages.add(sum / count);
25 }
26 return averages;
27 }
28 public static void main(String[] args) {
29 TreeNode a = new TreeNode(3);
30 TreeNode b = new TreeNode(9);
31 TreeNode c = new TreeNode(20);
32 TreeNode d = new TreeNode(15);
33 TreeNode e = new TreeNode(7);
34
35 a.left = b;
36 a.right = c;
37 c.left = d;
38 c.right = e;
39
40 Solution sol = new Solution();
41 List<Double> result = sol.averageOfLevels(a);
42 result.forEach(avg -> System.out.print(avg + " "));
43 }
44}The Java solution uses a queue for BFS. At each level of the tree, nodes are processed to compute sums and counts. Averages are computed at the end of each level. This approach efficiently calculates averages level by 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.
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode* node, int level, vector<double>& sums, vector<int>& counts) {
if (!node) return;
if (level >= sums.size()) {
sums.push_back(node->val);
counts.push_back(1);
} else {
sums[level] += node->val;
counts[level]++;
}
dfs(node->left, level + 1, sums, counts);
dfs(node->right, level + 1, sums, counts);
}
vector<double> averageOfLevels(TreeNode* root) {
vector<double> sums;
vector<int> counts;
dfs(root, 0, sums, counts);
for (int i = 0; i < sums.size(); ++i) {
sums[i] /= counts[i];
}
return sums;
}
int main() {
/* Create Binary tree with nodes */
TreeNode a(3), b(9), c(20), d(15), e(7);
a.left = &b;
a.right = &c;
c.left = &d;
c.right = &e;
vector<double> result = averageOfLevels(&a);
for (double avg : result) {
cout << avg << " ";
}
return 0;
}The C++ solution applies recursive DFS for traversing each node. Nodes are processed to update level sums and counts, with averages calculated post-recursion.