[Python] Simple solution using `None` markers for levels


#1
class Solution:
    # @param A : root node of tree
    # @return a list of list of integers
    def levelOrder(self, A):
        from collections import deque
        q = deque()
        result = []
        level = []
        if A:
            q.append(A)
            q.append(None)  # Marker signifying end of a level
        else:
            return []
        while len(q) > 0:
            item = q.popleft()
            if item:
                level.append(item.val)  # Creating a list of items in this level
                if item.left:
                    q.append(item.left)
                if item.right:
                    q.append(item.right)
            else:
                result.append(level)
                # Add None marker, only when there are items left to process, otherwise it will be infinite loop
                if len(q) > 0:
                    level = []
                    q.append(None)
        return result