Level Order Alternating

Given a binary tree root, return values of the nodes in each level, alternating from going left-to-right and right-to-left.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Level-Order-Alternating

Examples

Example 1

Input

• root =

Output

• answer = [3, 4, 0, 2, 1]

Solution