[LeetCode]#637. Average of Levels in Binary Tree

Environment: Python 3.8

Key technique: binarytree, Node, collections, deque

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].

Analysis:

1. Use collections.deque()
2. check node or not
3. get the same level node
4. search next level node
5. calculate the current level average and add it to answer list
6. return all levels average

Solution:

from binarytree import Node
root = Node(3) 
root.left=Node(9)
root.right=Node(20) 
root.right.left=Node(15)
root.right.right=Node(7)
# Getting binary tree 
print('Binary tree :', root)
import collections
class Solution(object):
    def averageOfLevels(self, root):
        queue = collections.deque()
        ans = []
        queue.append(root)
        while queue:
            size = len(queue)
            temp = []
            for _ in range(size):
                node = queue.popleft()
                if not node:
                    continue
                temp.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            if temp:
                ans.append(sum(temp) / float(len(temp)))
        return ans

Submissions:

Reference:

【LeetCode】637. Average of Levels in Binary Tree 解题报告（Python）_负雪明烛-CSDN博客

從零開始學Python (23) — 資料結構模組deque：旁人來來去去像行雲流水

Note: Not so good for node.