# Python solution using two stacks

• We can print spiral order traversal in O(n) time and O(n) extra space. The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left.

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def zigzagLevelOrder(self, root):
if not root:
return []

s1 = []
s2 = []
res = []
s1.append(root)

while len(s1) > 0 or len(s2) > 0:
local = []
while len(s1) > 0:
node = s1.pop()
local.append(node.val)
if node.left:
s2.append(node.left)
if node.right:
s2.append(node.right)

if len(local) > 0:
res.append(local)

local = []
while len(s2) > 0:
node = s2.pop()
local.append(node.val)
if node.right:
s1.append(node.right)
if node.left:
s1.append(node.left)

if len(local) > 0:
res.append(local)

return res
``````

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