Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Output: [3, 14.5, 11]
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].
Note: The range of node’s value is in the range of 32-bit signed integer.
Solution in python:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: ave =  queue = [root] num = 1 values, new_num= 0, 0 while queue: for i in range(num): node = queue.pop(0) values += node.val if node.left: queue.append(node.left) new_num += 1 if node.right: queue.append(node.right) new_num += 1 ave.append(values/num) num = new_num new_num, values = 0, 0 return ave
O(n). The whole tree is traversed atmost once. Here, n refers to the number of nodes in the given binary tree.
O(m). The size of queue or ave can grow upto atmost the maximum number of nodes at any level in the given binary tree. Here, m refers to the maximum mumber of nodes at any level in the input tree.