Question
Zigzag level order traversal of a Binary Tree
Given the root node of a binary tree, return the node values in zig-zag level order traversal.
Note: In zig zag traversal starting from the first level go from left to right for odd-numbered levels and right to left for even-numbered levels.
Note: In zig zag traversal starting from the first level go from left to right for odd-numbered levels and right to left for even-numbered levels.
Input
User Task
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function zigzag_level_order(), which takes the root node as its parameter.
Custom Input
The first line of input contains a positive integer N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Constraints
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function zigzag_level_order(), which takes the root node as its parameter.
Custom Input
The first line of input contains a positive integer N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Constraints
KaTeX can only parse string typed expression
KaTeX can only parse string typed expression
Output
Return a 2D list where each inner list represents one level of the tree.
Example
Input
6
1 2 3 4 5 -1 6
Output
1
3 2
4 5 6
Explanation
The below given image depicts the binary tree given in the input:
The arrows represents the direction of traversal for that level.
6
1 2 3 4 5 -1 6
Output
1
3 2
4 5 6
Explanation
The below given image depicts the binary tree given in the input:
The arrows represents the direction of traversal for that level.