If I remember correctly, list in python can be treated like a stack but not a queue.
To be more explicit, list in python has amortized constant time append() and pop().
Doing pop(0) to get the left most element is a linear time operation and should be strongly discouraged.
As list.pop(0) in python means a linear time, I used a
mark to simulate queue
Just remember where you have been and ignore the elements before
And my solution accepted is
def levelOrder(self, root): if not root: return  traversalList =  travel =  travel.append(root) mark = 0 while len(travel) > mark: # Use mark to tell where is the head of the "queue" temp =  while len(travel) > mark: temp.append(travel[mark]) mark += 1 traversalList.append([node.val for node in temp]) for node in temp: if node.left: travel.append(node.left) if node.right: travel.append(node.right) return traversalList
As sashimee suggested, use
collections.deque(). And you will get FIFO effect from
# import collections # looks to be automatically imported already q = collections.deque() q.appendleft(1) q.appendleft(2) q.appendleft(3) q.pop() # 1 q.pop() # 2 q.pop() # 3
As for the workaround of using
pop(0) to realize a queue, it's strongly discouraged. (you can refer to a good article 'Efficiency of using a Python list as a queue' on stackoverflow)
Though list objects support similar operations, they are optimized for fast fixed-length operations and
incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
collections.deque() instead of
list() for a FIFO queue
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.