637.Average_of_Levels_in_Binary_Tree_(Easy).md

637. Average of Levels in Binary Tree (Easy)

Date and Time: Jun 7, 2024, 12:37 PM (EST)

Link: https://leetcode.com/problems/average-of-levels-in-binary-tree/

Question:

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 1:

Input: root = [3, 9, 20, null, null, 15, 7]

Output: [3.00000, 14.50000, 11.00000]

Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Example 2:

Input: root = [3, 9, 20, 15, 7]

Output: [3.00000, 14.50000, 11.00000]

My Solution:

This is a BFS level order traversal, we use qLen to store how many nodes does this current level have and we can make sure we loop over all the nodes in each level. We pop() a node from deque and append its left and rigth into the deque for next level traversal. Then we update tmp += node.val, and append to res.append(tmp / qLen).

Similar question: 199. Binary Tree Right Side View (Medium)

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        # Use BFS
        res = []
        deque = collections.deque([root])
        while deque:
            qLen = len(deque)
            tmp = 0
            for i in range(qLen):
                node = deque.popleft()
                tmp += node.val
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
            res.append(tmp / qLen)
        return res