Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

Example:
Input: 1 / \ 20 3 / \ 5 15 Output: [ [1], [3, 20], [5, 15] ]

Solution

We can do level order traversal, instead of Queue we can use Stack to maintain the next level for the ZigZag pattern.

Code

Output

[[3], [20, 9], [15, 7]]

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *