A ski resort's slope is a binary tree of gates. A zigzag run starts at any gate and repeatedly descends to a child, but the direction must alternate: if you just took a left branch, the next branch must be right, and vice versa. The run may stop at any time. The length of a run is the number of branches taken (edges), so a run that visits a single gate has length 0.
Report the maximum length over all zigzag runs.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer gate id or null for a missing child. Children of null nodes are omitted. (Ids do not affect the answer.)
A single integer: the length (in branches) of the longest zigzag run.
Example 1
Input
4 1 null 2 3
Expected
2
Explanation
Start at the root, take the right branch to 2 (now you must go left), then the left branch to 3. That is two alternating branches, length 2, which is the longest.
Example 2
Input
3 1 2 3
Expected
1
Explanation
From the root you can take one branch (to 2 or to 3), but the child then has no branch in the required opposite direction. The best run has length 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →