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

"""
:type root: TreeNode
:rtype: List[float]
"""
# Definition for a binary tree node.
# class TreeNode: (= 'Binary Tree')
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# I think the codes above mean the condition that already set.

from collections import deque

class Solution:
    def averageOfLevels(self, root):
        
# you have to pop queue and initialize result to prevent 
# for avoiding continuous updating outside the 'while loof'.
        result = []
        q = deque()

    # At first, you have to append 'root' in the queue.
        q.append(root) 

    # loop until there is no q. 
        while q: 
            
            qlen = len(q)
            level = []
            
            for i in range(qlen):
                
                node = q.popleft()


    # This code is kind of 'for updating queue'.
    # Let's have a example of the case. 
    #          3
            # / \
            # 9  20
            #   /  \
            #  15   7

                if node:
                    level.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
# then, it will proceed like this.
# Loop 1: The queue q contains the root node [3]. 
# This node's value is added to level, 
# and its children nodes [9, 20] are added to the queue.

# Loop 2: Now, q contains [9, 20]. The values of these nodes are processed,
# and each of their children are added to the queue. 9 has no children, 
# whereas 20's children [15, 7] are added to the queue.

# Loop 3: At this point, q contains [15, 7]. 
# The values of these nodes are processed, 
# and there are no further children to add.

        # if there is no 'int'?
        # then, it will be viewd as 'float' type.
            if level: 
                result.append(sum(level)/len(level))
                
        return result

Key

1. How this while loop proceed?

Loop 1: The queue q contains the root node [3]. This node’s value is added to level, and its children nodes [9, 20] are added to the queue.

Loop 2: Now, q contains [9, 20]. The values of these nodes are processed, and each of their children are added to the queue. 9 has no children, whereas 20’s children [15, 7] are added to the queue.

Loop 3: At this point, q contains [15, 7]. The values of these nodes are processed, and there are no further children to add.

1. If you want to use ‘bfs’ or ‘binary tree’?

Then, use the ‘queue’ structure well like in this code contents. You have to remember this format to solve this kind of problem.