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