# Python with a queue and a stack

• ``````class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
queue = collections.deque()
stack = []
rst = []
layer = 0

if not root:    return []
stack.append(root)

#in every level, <int>n represent the #childnode in this level;
#                <list>temp represent the node.val in this level
#                <int>layer indicate left2right or right2left
while stack:
n = len(stack)
i = 0
temp = []
layer += 1

#store the childnode in queue.
while i < n:
p = stack.pop()
temp.append(p.val)
if layer % 2:
if p.left:  queue.appendleft(p.left)
if p.right: queue.appendleft(p.right)
else:
if p.right: queue.appendleft(p.right)
if p.left:  queue.appendleft(p.left)
i += 1
rst.append(temp)

#when level ends, stack.push(queue.pop())one by one.
j = 0
len_queue = len(queue)
while len(stack) < len_queue:
stack.append(queue.pop())
j += 1

return rst``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.