LeetCode //C - 1372. Longest ZigZag Path in a Binary Tree

1372. Longest ZigZag Path in a Binary Tree

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

Example 1:

Input root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> 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 -> right -> left -> right).

Example 3:

Input root = [1]
Output 0

Constraints:

• The number of nodes in the tree is in the range $[1,5?10^4]$.
• 1 <= Node.val <= 100

From: LeetCode
Link: 1372. Longest ZigZag Path in a Binary Tree

---

Solution:

Ideas：

1. Global Maximum Length: We keep a global variable or a pointer reference (longest) to store the maximum length of any ZigZag path we find in the tree.

2. Recursive Helper Function (updateZigZag): The helper function is designed to be called recursively for each node in the tree, and it performs the following actions:

• Base Case: If the current node is NULL, the function returns immediately because you can’t go any further down this path.
• Update Longest Path: If the current node is not NULL, the function checks if the current ZigZag length is greater than the global maximum length recorded so far. If it is, it updates the global maximum.
• Recursive Calls: The function makes two recursive calls:
  • One call is made to continue in the same direction as the current ZigZag path. This means if we went left to reach the current node, we now go right, and vice versa. The length is incremented by one since we are continuing the ZigZag path.
  • Another call is made to start a new ZigZag path in the opposite direction from the current node. This is because any node can potentially be the start of a longer ZigZag path. The length for this new path starts from 1.

3. Two Initial Calls: The longestZigZag function initializes the maximum length to zero and then makes two initial calls to the helper function: one assuming the ZigZag path starts by going left from the root, and another assuming it starts by going right.

4. Returning the Result: After the entire tree has been traversed, the longest variable will hold the length of the longest ZigZag path found in the tree. This value is then returned.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// Helper function to update the longest zigzag path
void updateZigZag(struct TreeNode* node, int direction, int length, int* longest) {
    if (!node) return;
    // Update the longest length found so far
    *longest = length > *longest ? length : *longest;
    // Continue in the ZigZag path
    if (direction == 0) {
        updateZigZag(node->left, 1, length + 1, longest); // Change direction to right
        updateZigZag(node->right, 0, 1, longest); // Reset length if changing direction
    } else {
        updateZigZag(node->right, 0, length + 1, longest); // Change direction to left
        updateZigZag(node->left, 1, 1, longest); // Reset length if changing direction
    }
}

int longestZigZag(struct TreeNode* root) {
    int longest = 0;
    updateZigZag(root, 0, 0, &longest); // Start with direction as left (0)
    updateZigZag(root, 1, 0, &longest); // Start with direction as right (1)
    return longest;
}