0637-average-of-levels-in-binary-tree

Try it on leetcode

Description

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]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Solution(Python)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
from collections import deque,defaultdict
class Solution:
    def averageOfLevels(self, root: TreeNode | None) -> list[float]:
        # runningSUm = 0
        #  add root.val
        #   average = running_sum // count_of nodes
        # level 0 running_sum 0 count_nodes 0
        #   3 l 1 ; s = 3 c = 1 
        #    avg = 3.00
        #  
        return self.dfs(root)

    def dfs(self, root: TreeNode | None) -> list[float]:
        levels = defaultdict(lambda: [0.0, 0])
        def dfs(node, depth):
            if not node:
                return 
            levels[depth][0] += node.val
            levels[depth][1] += 1
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        dfs(root, 0)
        return [levels[i][0] / levels[i][1] for i in range(len(levels))]
    # TIme xoplexity: O(n)
    # Sapce Compleity: O(M) N/2
    def bfs(self, root: TreeNode | None) -> list[float]:
        res = []
        q= deque([root])

        while q:
            level_size = len(q)
            running_sum = 0
            for _ in range(level_size):
                node = q.popleft()
                running_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            avg = running_sum/level_size
            res.append(avg)
        return res