Use Breadth-First Search (level-order traversal) with a queue. For each level, sum all node values and divide by the number of nodes at that level to get the average. Append each level's average to the result list.
Use Depth-First Search to traverse the tree, maintaining a list of (sum, count) tuples for each level. After the traversal, compute the average for each level by dividing the sum by the count.
""" 0637.1 - Average of Levels in Binary Tree - Solution 1 - BFS with Queue """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
"""Average of Levels in Binary Tree Function"""
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_sum / level_size)
return result
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: root = [3,9,20,null,null,15,7] -> [3.0, 14.5, 11.0]
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().averageOfLevels(root1))
# Example 2: root = [3,9,20,15,7] -> [3.0, 14.5, 11.0]
root2 = TreeNode(3, TreeNode(9, TreeNode(15), TreeNode(7)), TreeNode(20))
print(Solution().averageOfLevels(root2))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0637.2 - Average of Levels in Binary Tree - Solution 2 - DFS with Level Tracking """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
"""Average of Levels in Binary Tree Function"""
levels = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(levels):
levels.append([0, 0])
levels[depth][0] += node.val
levels[depth][1] += 1
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
return [s / c for s, c in levels]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: root = [3,9,20,null,null,15,7] -> [3.0, 14.5, 11.0]
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().averageOfLevels(root1))
# Example 2: root = [3,9,20,15,7] -> [3.0, 14.5, 11.0]
root2 = TreeNode(3, TreeNode(9, TreeNode(15), TreeNode(7)), TreeNode(20))
print(Solution().averageOfLevels(root2))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()