856. Zigzag Level Order Traversal

Given the root of a binary tree, return its zigzag level-order traversal — values level by level, alternating left-to-right on the first level, right-to-left on the next, and so on. Return the result as a nested array. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Nested array — values per level in zigzag order.

Examples

Input: [1,2,3,4,5,6,7]
Output: [[1],[3,2],[4,5,6,7]]
Explanation: Levels alternate direction.

Input: [1]
Output: [[1]]
Explanation: Single level.

Input: []
Output: []
Explanation: Empty tree.

Constraints

• 0<=nodes<=10^4
• -1000<=value<=1000

Asked by