Longest ZigZag Path in a Binary Tree

A more efficient approach is to use a single Depth First Search (DFS) pass. By employing a post-order traversal, we can compute the necessary information for a node based on the results from its children. For each node, we calculate the length of the longest ZigZag path starting at that node and going left, and the length of the path starting at that node and going right. This information is then 'bubbled up' to the parent node, which uses it to compute the lengths of its own starting paths. A global variable is used to keep track of the maximum length found at any point in the traversal.

• Use a single Depth First Search (DFS) traversal, specifically a post-order traversal.
• Define a recursive helper function, dfs(node), that returns information about paths starting at node.
• The dfs(node) function will return an array of two integers: [leftPath, rightPath].
  • leftPath: The length of the longest ZigZag path that starts at node and first goes to the left.
  • rightPath: The length of the longest ZigZag path that starts at node and first goes to the right.
• The base case for the recursion is when node is null. In this case, return [-1, -1] to indicate that no path exists, which simplifies the calculation for the parent.
• For a non-null node, recursively call dfs on its children: leftResult = dfs(node.left) and rightResult = dfs(node.right).
• To calculate leftPath for the current node: a path going left from node must then continue from node.left by going right. So, leftPath = 1 + leftResult[1].
• Similarly, rightPath = 1 + rightResult[0].
• Maintain a global maxLength variable. After computing leftPath and rightPath for the current node, update maxLength = max(maxLength, leftPath, rightPath).
• The dfs function returns the [leftPath, rightPath] array for its parent to use.

This optimal solution avoids re-computation by solving the problem in a single pass using a post-order DFS traversal. The core idea is to use the return value of the recursive calls to pass information up the tree.

Our recursive function, dfs(node), will return an array of two integers for each node. The first element will be the length of the longest ZigZag path starting at node with a left move, and the second will be the length of the path starting with a right move.

When dfs(node) is called:

1. It first calls itself on its left and right children.
2. It receives the results from its children. For example, leftResult from dfs(node.left) contains the lengths of paths starting at node.left.
3. To find the length of a ZigZag path starting at node and going left, we take one step to node.left (length 1) and then continue the ZigZag. The next move must be to the right. The length of the longest ZigZag path starting from node.left and going right is given by leftResult[1]. So, the total length is 1 + leftResult[1].
4. Similarly, the length of a path starting at node and going right is 1 + rightResult[0].
5. We update a global maxLength with the maximum of these two calculated lengths. This ensures we track the longest path found anywhere in the tree.
6. Finally, the function returns the newly computed lengths for node to its parent.

/**
 * 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 {
    int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root);
        return maxLength;
    }

    /**
     * Performs a post-order traversal to calculate ZigZag path lengths.
     * @return an array of two elements:
     *         result[0] = longest ZigZag path starting from 'node' and going LEFT.
     *         result[1] = longest ZigZag path starting from 'node' and going RIGHT.
     */
    private int[] dfs(TreeNode node) {
        if (node == null) {
            // Base case: no path exists from a null node.
            // -1 helps in calculation: 1 + (-1) = 0 for a path of a single node.
            return new int[]{-1, -1};
        }

        // Recursively get results from children
        int[] leftResult = dfs(node.left);
        int[] rightResult = dfs(node.right);

        // Calculate path starting at current node and going left.
        // This path continues from the left child by going right.
        int pathStartingLeft = 1 + leftResult[1];

        // Calculate path starting at current node and going right.
        // This path continues from the right child by going left.
        int pathStartingRight = 1 + rightResult[0];

        // Update the global maximum length found so far.
        maxLength = Math.max(maxLength, Math.max(pathStartingLeft, pathStartingRight));

        // Return the lengths of paths starting at the current node for the parent.
        return new int[]{pathStartingLeft, pathStartingRight};
    }
}