1. You are given a partially written function to solve.
2. Given a binary tree root, a ZigZag path for a binary tree is defined as follow:
a. Choose any node in the binary tree and a direction (right or left).
b. If the current direction is right then move to the right child of the current node otherwise move to the left child.
c. Change the direction from right to left or right to left.
d. Repeat the second and third step until you can't move in the tree.
3.Zigzag length is defined in terms of edges. (A single node has a length of 0).
4. Return the longest ZigZag path contained in that tree.Input Format
Input is managed for you.
Output Format
Output is managed for you.
Constraints
0 <= Number of Nodes <= 10^9 -10^9 <= value of Node data <= 10^9
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
15 1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1
Output
4