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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, x):
5 self.val = x
6 self.left = None
7 self.right = None
8
9class Solution:
10 def averageOfLevels(self, root):
11 if not root:
12 return []
13 averages = []
14 queue = deque([root])
15 while queue:
16 level_sum, level_count = 0, len(queue)
17 for _ in range(level_count):
18 node = queue.popleft()
19 level_sum += node.val
20 if node.left:
21 queue.append(node.left)
22 if node.right:
23 queue.append(node.right)
24 averages.append(level_sum / level_count)
25 return averages
26
27# Example Usage
28if __name__ == "__main__":
29 a = TreeNode(3)
30 b = TreeNode(9)
31 c = TreeNode(20)
32 d = TreeNode(15)
33 e = TreeNode(7)
34 a.left = b
35 a.right = c
36 c.left = d
37 c.right = e
38
39 solution = Solution()
40 result = solution.averageOfLevels(a)
41 print(result)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.
This C solution employs a depth-first approach that recursively calculates level sums and counts. The dfs function updates these for each node, with results computed for levels in the end.