def zig_zag_traversal(root: Node) -> List[List[int]]:
ans = []
q = deque([root])
# Do level order traversal
while q:
n = len(q)
vals = []
for i in range(n):
node = q.popleft()
vals.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(vals)
# Reverse every other level using mod
for i in range(len(ans)):
if i % 2 != 0:
ans[i] = reversed(ans[i])
return ans
Looks very complicated but interesting solution.
I tried the same route but gave up and turned to another solution in the end.