Given a binary tree, return its level order traversal but in alternating left-to-right order. The first level is read left to right, the second right to left, the third left to right, and so on.
Use a BFS traversal that records each level as its own list, then reverses every other level before appending it to the result.
Input
root: the root node of a binary tree, given in level-order array form where null marks a missing child
Output
A list of lists, where each inner list contains the node values at one level in the appropriate (alternating) direction.
Examples
Example 1
Inputroot = [1, 2, 3]
Output[[1], [3, 2]]
Explanation: Level 0 reads left to right ([1]); level 1 reverses to [3, 2].
Example 2
Inputroot = [1, 2, 3, 4, 5, null, 6]
Output[[1], [3, 2], [4, 5, 6]]
Explanation: Level 0 is [1]; level 1 reverses [2, 3] to [3, 2]; level 2 stays left to right as [4, 5, 6].
Example 3
Inputroot = [1]
Output[[1]]
Explanation: A single node forms one level read left to right.
Constraints
If the root is null, return an empty list.
Levels are zero-indexed; even-indexed levels go left to right and odd-indexed levels go right to left.