LeetCode: 103. Binary Tree Zigzag Level Order Traversal

2026-03-31

Level order usually suggests BFS, but DFS with depth tracking also works well.

103. Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

Summary

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (from left to right, then right to left for the next level, and so on).

Approach

Use pre-order traversal, then reorder the values at each depth.

Function

Initialization:

  • ans = defaultdict(list)

Function traverse(root, depth): If root: append root.val to ans[depth] traverse(root.left, depth + 1) traverse(root.right, depth + 1)

Main:

traverse(root, 0) zigzag = [] For i, arr in enumerate(ans.values()): If i % 2 == 1: arr.reverse() zigzag.append(arr) Return zigzag

Complexity

Time Complexity: O(N) Space Complexity: O(N)