Return the level order traversal of a binary tree, but alternate the direction of values on each level.
Problem
Given the root of a binary tree, return the values of its nodes level by level. The first level should be read from left to right, the second from right to left, the third from left to right, and so on, alternating the direction for every level.
You should group the values by level and preserve the zigzag ordering within each group.
Input Format
- A binary tree root node
root. - Each tree node contains an integer value and references to its left and right children.
Output Format
- Return a 2D list where each inner list contains the node values for one level in zigzag order.
Constraints
- The tree may be empty.
- Node values may be any integers.
- The traversal should visit each node exactly once.
Hints
- Use a level-order traversal structure to process one level at a time.
- Track whether the current level should be reversed before appending it to the result.
- There are multiple ways to implement the alternating order efficiently without sorting.
Constraints
- The tree may be empty.
- Visit each node once.
- Alternate the traversal direction at every level.
Example 1
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]
Explanation
Level 0 is left to right: [3]. Level 1 is right to left: [20, 9]. Level 2 is left to right: [15, 7].
Example 2
Input
root = [1,2,3,4,null,null,5]
Output
[[1],[3,2],[4,5]]
Explanation
The traversal alternates direction on each level while still grouping nodes by depth.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.