Python 0103.py
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# similiar to problem 102
levels = defaultdict(list)
def deeper(node, depth):
if node:
levels[depth].append(node.val)
deeper(node.left, depth+1)
deeper(node.right, depth+1)
deeper(root, 0)
for l in levels.keys():
if l % 2 == 1:
levels[l] = reversed(levels[l])
return [ levels[l] for l in sorted(levels.keys()) ]
Difficulty
and has an acceptance rate of about 64% (2+ million submissions).
Typical patterns to solve this problem:
- Binary Tree
- Breadth First Search
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a method zigzagLevelOrder that returns the values of a binary tree in a zig-zag (alternating left-to-right and right-to-left) level order traversal. The algorithm first collects node values per depth using a depth-first recursion, then reverses the order of values on every odd-indexed level, and finally assembles the result in increasing depth order.
Key Steps
The method begins by creating a dictionary that maps each depth to a list of node values encountered at that depth.
levels = defaultdict(list)
A nested helper function deeper performs a pre-order depth-first walk. For each non-null node it records the node’s value in the list associated with the current depth, then recurses on the left child followed by the right child, incrementing the depth counter.
def deeper(node, depth):
if node:
levels[depth].append(node.val)
deeper(node.left, depth+1)
deeper(node.right, depth+1)
The recursion is initiated with the root node at depth zero.
deeper(root, 0)
After the traversal, the code iterates over the collected depth keys. For each odd depth it replaces the list with a reversed iterator, thereby achieving the required right-to-left ordering for those levels.
for l in levels.keys():
if l % 2 == 1:
levels[l] = reversed(levels[l])
Finally, the method builds the output list by extracting the values for each depth in sorted order, preserving the original or reversed ordering as appropriate.
return [ levels[l] for l in sorted(levels.keys()) ]
Edge Cases Handled
When the input root is None, the recursive helper receives a null node immediately, performs no append operation, and the levels dictionary remains empty. The subsequent loop over levels.keys() does nothing, and the final list comprehension yields an empty list, correctly representing an empty tree.
If the tree consists of a single node, the recursion records the node’s value at depth zero. Since depth zero is even, no reversal occurs, and the result is a list containing a single inner list with that value.
The use of defaultdict(list) ensures that any depth encountered for the first time is automatically associated with an empty list, eliminating the need for explicit existence checks before appending.
Reversal is applied only to odd depths, so levels that naturally appear left-to-right (even depths) retain their original order without additional processing.
Performance Optimizations
The algorithm leverages a single depth-first traversal to populate all levels, avoiding the need for multiple passes or auxiliary queues typically used in breadth-first approaches. By storing values directly into a dictionary keyed by depth, the method eliminates repeated list concatenations.
The reversal step uses Python’s built-in reversed iterator, which provides a lazy view of the list in reverse order without creating a new list copy. This reduces memory overhead for large levels where a full copy would be unnecessary.
Sorting the depth keys before constructing the final result incurs a cost proportional to the number of distinct depths, which is bounded by the height of the tree. Since the number of depths is usually far smaller than the total node count, this sorting step has minimal impact on overall performance.
Collecting all node values during the recursive walk ensures that each node is visited exactly once, leading to a linear traversal cost relative to the number of nodes. The combination of a single pass, lazy reversal, and efficient dictionary access results in a solution that scales well for deep or wide binary trees.
ELI5 - Simplified Explanation
Imagine a giant tree made of numbers. To read them, you start at the very top and look at each row one by one. The code starts at the top and visits every single number in the tree, grouping them together based on how far down they are. Every row gets its own special basket.
Once every number is tucked into its correct row basket, the code looks at them again. It decides to leave the first row exactly as it is. For the next row down, it turns the numbers around so they are in backwards order. It keeps switching back and forth like this, leaving one row normal and flipping the next one, all the way down the tree. It looks just like a zigzagging path through the branches. The final result is a list of these baskets, arranged perfectly from top to bottom with some rows walking in reverse.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||||
| WalkCCC | C++ | Python | Java | ||||||||||
| leetcode.ca | C++ | Python | Java | Rust | JS | Go | TS | ||||||
| LeetcodeHelp | C++ | Python | Java | ||||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||||
| Progiez | C++ | Python | Java | ||||||||||
| github | AdelDaniel | Dart | |||||||||||
| aylei | Rust | ||||||||||||
| begeekmyfriend | C | ||||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| chenyanzhe | C++ | ||||||||||||
| everthis | JS | ||||||||||||
| fartem | Ruby | ||||||||||||
| FelixFan1122 | C# | ||||||||||||
| fengvyi | C++ | ||||||||||||
| gaosq0604 | Python | ||||||||||||
| Garvit244 | Python | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JS | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| lennylxx | C++ | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| luangong | C++ | ||||||||||||
| MacJim | C++ | ||||||||||||
| qiyuangong | Python | ||||||||||||
| ruoru | Rust | ||||||||||||
| shreymehul | C# | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| vthwang | Java | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| yuanliu666 | Kotlin | ||||||||||||
| YuriSpiridonov | Python | ||||||||||||
| zfang399 | C++ | ||||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||||
| WalkCCC | C++, Python, Java | ||||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||||
| Progiez | C++, Java, Python | ||||||||||||
| AdelDaniel | Dart | ||||||||||||
| aylei | Rust | ||||||||||||
| begeekmyfriend | C | ||||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | Python, Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| chenyanzhe | C++ | ||||||||||||
| everthis | JavaScript | ||||||||||||
| fartem | Ruby | ||||||||||||
| FelixFan1122 | C# | ||||||||||||
| fengvyi | C++ | ||||||||||||
| gaosq0604 | Python | ||||||||||||
| Garvit244 | Python | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JavaScript | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| lennylxx | C++ | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| luangong | C++ | ||||||||||||
| MacJim | C++ | ||||||||||||
| qiyuangong | Python | ||||||||||||
| ruoru | Rust | ||||||||||||
| shreymehul | C# | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| vthwang | Java | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| yuanliu666 | Kotlin | ||||||||||||
| YuriSpiridonov | Python | ||||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 102: Binary Tree Level Order Traversal
- problem 314: Binary Tree Vertical Order Traversal
Solved On The Same Day
- problem 110: Balanced Binary Tree
- problem 111: Minimum Depth of Binary Tree
- problem 118: Pascal's Triangle
- problem 119: Pascal's Triangle II
- problem 228: Summary Ranges
- problem 530: Minimum Absolute Difference in BST
- problem 82: Remove Duplicates from Sorted List II
- problem 102: Binary Tree Level Order Traversal
- problem 105: Construct Binary Tree from Preorder and Inorder Traversal
- problem 106: Construct Binary Tree from Inorder and Postorder Traversal
- problem 107: Binary Tree Level Order Traversal II
- problem 109: Convert Sorted List to Binary Search Tree
- problem 117: Populating Next Right Pointers in Each Node II
- problem 128: Longest Consecutive Sequence
- problem 138: Copy List with Random Pointer
- problem 150: Evaluate Reverse Polish Notation
- problem 155: Min Stack
- problem 209: Minimum Size Subarray Sum
- problem 274: H-Index
- problem 380: Insert Delete GetRandom O(1)
- problem 427: Construct Quad Tree
- problem 452: Minimum Number of Arrows to Burst Balloons
- problem 30: Substring with Concatenation of All Words
- problem 37: Sudoku Solver
- problem 44: Wildcard Matching
- problem 1326: Minimum Number of Taps to Open to Water a Garden
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality