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].
The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1
Solutions
Solution 1: BFS
We can use the Breadth-First Search (BFS) method to traverse the nodes of each level and calculate the average value of each level.
Specifically, we define a queue $q$, initially adding the root node to the queue. Each time, we take out all the nodes in the queue, calculate their average value, add it to the answer array, and then add their child nodes to the queue. Repeat this process until the queue is empty.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defaverageOfLevels(self,root:Optional[TreeNode])->List[float]:q=deque([root])ans=[]whileq:s,n=0,len(q)for_inrange(n):root=q.popleft()s+=root.valifroot.left:q.append(root.left)ifroot.right:q.append(root.right)ans.append(s/n)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcaverageOfLevels(root*TreeNode)[]float64{q:=[]*TreeNode{root}ans:=[]float64{}forlen(q)>0{n:=len(q)s:=0fori:=0;i<n;i++{root=q[0]q=q[1:]s+=root.Valifroot.Left!=nil{q=append(q,root.Left)}ifroot.Right!=nil{q=append(q,root.Right)}}ans=append(ans,float64(s)/float64(n))}returnans}
We can also use the Depth-First Search (DFS) method to calculate the average value of each level.
Specifically, we define an array $s$, where $s[i]$ is a tuple representing the sum of node values and the number of nodes at the $i$-th level. We perform a depth-first search on the tree. For each node, we add the node's value to the corresponding $s[i]$ and increment the node count by one. Finally, for each $s[i]$, we calculate the average value and add it to the answer array.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819202122
# 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 = rightclassSolution:defaverageOfLevels(self,root:Optional[TreeNode])->List[float]:defdfs(root,i):ifrootisNone:returniflen(s)==i:s.append([root.val,1])else:s[i][0]+=root.vals[i][1]+=1dfs(root.left,i+1)dfs(root.right,i+1)s=[]dfs(root,0)return[a/bfora,bins]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcaverageOfLevels(root*TreeNode)[]float64{s:=[]int{}cnt:=[]int{}vardfsfunc(root*TreeNode,iint)dfs=func(root*TreeNode,iint){ifroot==nil{return}iflen(s)==i{s=append(s,root.Val)cnt=append(cnt,1)}else{s[i]+=root.Valcnt[i]++}dfs(root.Left,i+1)dfs(root.Right,i+1)}dfs(root,0)ans:=[]float64{}fori,t:=ranges{ans=append(ans,float64(t)/float64(cnt[i]))}returnans}