You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:


	Choose any node in the binary tree and a direction (right or left).
	If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
	Change the direction from right to left or from left to right.
	Repeat the second and third steps until you can't move in the tree.


Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

&nbsp;
Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -&gt; left -&gt; right).


Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -&gt; right -&gt; left -&gt; right).


Example 3:

Input: root = [1]
Output: 0


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 5 * 104].
	1 &lt;= Node.val &lt;= 100


class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def helper(root):
            if root is None:
                return -1, -1

            leftRight = helper(root.left)[1] + 1
            rightLeft = helper(root.right)[0] + 1
            self.res = max(self.res, leftRight, rightLeft)
            return leftRight, rightLeft

        helper(root)
        return self.res
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
   static class Pair{
       int left=-1;
       int right=-1;
       int maxLen=0;
   }
    public int longestZigZag(TreeNode root) {
        Pair ans=longestZigZag_(root);
        return ans.maxLen;
    }

    public Pair longestZigZag_(TreeNode root) {
        if(root==null)
            return new Pair();
        Pair l=longestZigZag_(root.left);
        Pair r=longestZigZag_(root.right);

        Pair myAns=new Pair();
        myAns.left=l.right+1;
        myAns.right=r.left+1;
        int max=Math.max(myAns.left,myAns.right);
        myAns.maxLen=Math.max(max,Math.max(l.maxLen,r.maxLen));
        return myAns;

    }

}
class Solution {
    typedef long long ll;
    typedef pair<ll, ll> pi;
public:
    ll ans = 0;
    pi func(TreeNode* nd) {
        if(!nd){
            return {-1,-1};
        }
        pi p = { func(nd->left).second + 1, func(nd->right).first + 1 };
        ans = max({ans, p.first, p.second});
        return p;
    }
    int longestZigZag(TreeNode* root) {
        func(root);
        return ans;
    }
};
/** https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestZigZag = function(root) {
  this.out = 0;

  // Recursive left and right node and find the largest height
  let left = dfs(root.left, false) + 1;
  let right = dfs(root.right, true) + 1;
  this.out = Math.max(this.out, Math.max(left, right));
  
  return this.out;
};

var dfs = function(node, isLeft) {
  // Node is null, we return -1 because the caller will add 1, so result in 0 (no node visited)
  if (node == null) {
    return -1;
  }
  
  // No left or right node, we return 0 because the caller will add 1, so result in 1 (visited 1 node - this one)
  if (node.left == null && node.right == null) {
    return 0;
  }
  
  // Recursive to see which one is higher, zigzag to left or zigzag to right
  let left = dfs(node.left, false) + 1;
  let right = dfs(node.right, true) + 1;
  this.out = Math.max(this.out, Math.max(left, right));
  
  return isLeft === true ? left : right;
};
Longest ZigZag Path in a Binary Tree