Longest ZigZag Path in a Binary Tree

Hard

A ZigZag path alternates direction (left, right, left, ...) at each step. Its length is the number of edges visited. Given the root of a binary tree, return the length of the longest ZigZag path contained in it.

Example 1

Input:  root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3

Example 2

Input:  root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4

Example 3

Input:  root = [1]
Output: 0

Constraints

• 1 <= number of nodes <= 5*10^4
• 1 <= Node.val <= 100.