問題
原文
Given the
root
of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within10-5
of the actual answer will be accepted.
Example 1:
1234 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:
12 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
内容
二分木rootが与えられるので、各階層の値の平均値を配列で返してください。
誤差は10^(-5)以内としてください。
※正しくない可能性があります。
解答
解答1:Python, BFS(幅優先探索)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# 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: Optional[TreeNode]) -> List[float]: if not root: return None answer = [] q = deque() q.append(root) while q: sum_of_value = 0 length_of_q = len(q) for node in range(len(q)): node = q.popleft() if node.val:sum_of_value += node.val if node.left: q.append(node.left) if node.right: q.append(node.right) answer.append(sum_of_value/length_of_q) return answer |
幅優先探索
各階層の探索を行う際、valの合計値をsum_of_valueに、各階層のノードの数をlength_of_qにそれぞれ保存しておき、各階層の探索終了時に平均値を求めてanswerに追加する。
解答2:
メモ・参考・感想
コメント