Longest ZigZag Path in a Binary Tree

• 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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxLength = 0;18 19    public int longestZigZag(TreeNode root) {20        dfs(root);21        return maxLength;22    }23 24    /**25     * Performs a post-order traversal to calculate ZigZag path lengths.26     * @return an array of two elements:27     *         result[0] = longest ZigZag path starting from 'node' and going LEFT.28     *         result[1] = longest ZigZag path starting from 'node' and going RIGHT.29     */30    private int[] dfs(TreeNode node) {31        if (node == null) {32            // Base case: no path exists from a null node.33            // -1 helps in calculation: 1 + (-1) = 0 for a path of a single node.34            return new int[]{-1, -1};35        }36 37        // Recursively get results from children38        int[] leftResult = dfs(node.left);39        int[] rightResult = dfs(node.right);40 41        // Calculate path starting at current node and going left.42        // This path continues from the left child by going right.43        int pathStartingLeft = 1 + leftResult[1];44 45        // Calculate path starting at current node and going right.46        // This path continues from the right child by going left.47        int pathStartingRight = 1 + rightResult[0];48 49        // Update the global maximum length found so far.50        maxLength = Math.max(maxLength, Math.max(pathStartingLeft, pathStartingRight));51 52        // Return the lengths of paths starting at the current node for the parent.53        return new int[]{pathStartingLeft, pathStartingRight};54    }55}

• Create a main function longestZigZag(root) that initializes a global maximum length variable, maxLength, to 0.
• This function will call a traversal function, traverse(node), on the root to visit every node in the tree.
• The traverse(node) function will iterate through the tree (e.g., using pre-order traversal).
• For each node visited, it will calculate the longest ZigZag path starting from this node.
• To do this, it will simulate two paths:
  1. A path starting by moving to the left child.
  2. A path starting by moving to the right child.
• An iterative loop can be used for this simulation. For a path starting left, it moves to node.left, increments the length, then alternates between moving right and left until it hits a null node.
• During this simulation, maxLength is updated at each step.
• The same process is repeated for a path starting to the right.
• After the traverse function has visited all nodes, maxLength will hold the final answer.

The brute-force method systematically explores every possible ZigZag path. We can achieve this by traversing the entire tree. For every single node we encounter, we consider it as the starting point of a new ZigZag path. Since a path can begin by going either left or right, we explore both possibilities from each node.

We can implement a traverse function that visits each node. Inside this function, for the current node, we will have two loops. One loop simulates a ZigZag path starting with a left turn, and the other simulates a path starting with a right turn. These loops follow the alternating path rule, incrementing a counter for the length at each step and updating a global maximum. This ensures that we check every path starting from every node.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxLength = 0;18 19    public int longestZigZag(TreeNode root) {20        traverse(root);21        return maxLength;22    }23 24    private void traverse(TreeNode node) {25        if (node == null) {26            return;27        }28 29        // Calculate longest ZigZag path starting at the current node30        // Case 1: Path starts by going left31        calculatePath(node.left, false, 1); // Next move must be right32        // Case 2: Path starts by going right33        calculatePath(node.right, true, 1); // Next move must be left34 35        // Traverse the rest of the tree36        traverse(node.left);37        traverse(node.right);38    }39 40    // Helper to trace a single ZigZag path and update maxLength41    private void calculatePath(TreeNode node, boolean goLeft, int length) {42        if (node == null) {43            // Path ended at the parent of this null node.44            // The actual path length is length - 1.45            maxLength = Math.max(maxLength, length - 1);46            return;47        }48 49        maxLength = Math.max(maxLength, length);50 51        if (goLeft) {52            // Current direction is left, so next must be right53            calculatePath(node.left, false, length + 1);54        } else {55            // Current direction is right, so next must be left56            calculatePath(node.right, true, length + 1);57        }58    }59}