Zigzag Level Order Traversal
Medium
Given a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1
Input
[ [ 3, 9, 20, null, null, 15, 7 ] ]
Output
[ [ 3 ], [ 20, 9 ], [ 15, 7 ] ]
Explanation. Level 1: [3], Level 2: [20,9] (Right to Left), Level 3: [15,7] (Left to Right).
Example 2
Input
[ [ 1, 2, 3, 4, null, null, 5 ] ]
Output
[ [ 1 ], [ 3, 2 ], [ 4, 5 ] ]
Explanation. Level 1: [1], Level 2: [3,2] (Right to Left), Level 3: [4,5] (Left to Right).
Example 3
Input
[ [] ]
Output
[]
Explanation. The tree is empty, so the zigzag level order traversal is also an empty list.
Follow-up: Can you solve the problem without using additional data structures for the level order output?
Constraints:
The number of nodes in the tree is in the range [0, 2000]. Each node's value is between [-10^4, 10^4].
- Views
- 14