<p>You are given the <code>root</code> of a binary tree.</p>

<p>A ZigZag path for a binary tree is defined as follow:</p>

<ul>
	<li>Choose <strong>any </strong>node in the binary tree and a direction (right or left).</li>
	<li>If the current direction is right, move to the right child of the current node; otherwise, move to the left child.</li>
	<li>Change the direction from right to left or from left to right.</li>
	<li>Repeat the second and third steps until you can&#39;t move in the tree.</li>
</ul>

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

<p>Return <em>the longest <strong>ZigZag</strong> path contained in that tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/22/sample_1_1702.png" style="width: 221px; height: 383px;" />
<pre>
<strong>Input:</strong> root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Longest ZigZag path in blue nodes (right -&gt; left -&gt; right).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.png" style="width: 157px; height: 329px;" />
<pre>
<strong>Input:</strong> root = [1,1,1,null,1,null,null,1,1,null,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Longest ZigZag path in blue nodes (left -&gt; right -&gt; left -&gt; right).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> root = [1]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 5 * 10<sup>4</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        """
        for each recursion, keep track of if we got to the current node by going left or right
        based on that, when we call the recurion on left and right nodes, we can either reset the path length or add to it
        for each recusion keep track of the curr path length and update the maximum
        
        output = 0
        def dfs(node, path_length, prev_direction):
            if not node:
                return

            output = max(output, path_length)
            if prev_direction == left:
                dfs(right node, path_length + 1, right direction)
            else:
                dfs(right node, 1, right_direction)

            if prev_direction == right:
                dfs(left node, path_length + 1, left direction)
            else:
                dfs(left node, 1, left direction)
            return
        dfs(root, 1, left)
        dfs(root, 1, right)

        return output
        """
        
        output = 0
        def dfs(node, path_length, prev_direction):
            nonlocal output
            if not node:
                return

            output = max(output, path_length)
            if prev_direction == "left":
                dfs(node.right, path_length + 1, "right")
                dfs(node.left, 1, "left")
            else:
                dfs(node.right, 1, "right")
                dfs(node.left, path_length + 1, "left")
            
            return

        dfs(root, 0, "left")
        dfs(root, 0, "right")
        return output
        
230