637. Average of Levels in Binary Tree

Problem Statement

link: LeetCode.cn LeetCode

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:

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

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

Solution Approach

The algorithm uses a breadth-first search (BFS) to traverse the binary tree level by level, calculates the average of node values for each level, and appends these averages to the result list.

Algorithm

1. Breadth-First Search (BFS): The algorithm uses BFS to traverse the binary tree level by level, ensuring each node at a given level is processed together.
2. Level-wise Aggregation: For each level, it calculates the sum of node values and then computes the average by dividing the sum by the number of nodes at that level.
3. Queue for Level Processing: A queue (using collections.deque) is employed to efficiently manage nodes at each level and facilitate their sequential processing.

Complexity

time complexity: O(n) space complexity: O(W) W is the maximum width of the tree

Implement

    
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        q = collections.deque([root])
        result = []
        while q:
            n = len(q)
            total = 0
            for i in range(n):
                cur = q.popleft()
                total += cur.val
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            result.append(total / n)
        return result
                

    
    

Twitter  facebook  Email