Teaching Kids Programming: Videos on Data Structures and Algorithms
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,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]
Compute the Average of the Levels in Binary Tree using BFS Algorithm
As we are expanding the nodes of the next level in binary tree using Breadth First Search, we can compute the average then and push it to the result.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | # 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 class Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: if not root: return [] q = deque([root]) ans = [] while q: n = len(q) s = 0 for _ in range(n): cur = q.popleft() s += cur.val if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) ans.append(s/n) return ans |
# 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 class Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: if not root: return [] q = deque([root]) ans = [] while q: n = len(q) s = 0 for _ in range(n): cur = q.popleft() s += cur.val if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) ans.append(s/n) return ans
The time complexity is O(N) where N is the number of the nodes in binary tree and the space complexity is O(N) as we are using a queue to implement the Breadth First Search algorithm.
See also: How to Compute Average of Levels in Binary Tree?
We can use the Depth First Search Algorithm to compute the average levels of the binary tree: Teaching Kids Programming – Average Level of Binary Tree via Depth First Search Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to List the Boot Configuration Properties on Windows using VBScript?
Next Post: Javascript (NodeJS) Function to Get the Downvote Power of Account on Steem Blockchain