Here's the BFS approach with a direction flag. You process each level in the queue as usual, then conditionally reverse the collected values.
function zigzagLevelOrder(root):
if root is null:
return []
result = []
queue = [root]
leftToRight = true
while queue is not empty:
levelSize = queue.length
levelValues = []
for i from 0 to levelSize - 1:
node = queue.dequeue()
levelValues.append(node.val)
if node.left is not null:
queue.enqueue(node.left)
if node.right is not null:
queue.enqueue(node.right)
if not leftToRight:
reverse levelValues
result.append(levelValues)
leftToRight = not leftToRight
return result