Introduction

In this blog post, we will explore how to solve the LeetCode problem "1372" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 * 104]. 1 <= Node.val <= 100

Explanation

• Depth-First Search (DFS): Traverse the tree using DFS, keeping track of the current path length and direction (left or right).
  • Maximize Path Length: At each node, explore both left and right paths, alternating directions and updating the maximum ZigZag length found so far.
  • Resetting Paths: When a path cannot continue in a given direction, the path length from the next direction starts from 0.

• Runtime Complexity: O(N), where N is the number of nodes in the tree. Storage Complexity: O(H), where H is the height of the tree (worst case O(N) for skewed tree, average case O(log N) for balanced tree).

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def longestZigZag(root: TreeNode) -> int:
    """
    Finds the longest ZigZag path in a binary tree.

    Args:
        root: The root of the binary tree.

    Returns:
        The length of the longest ZigZag path.
    """

    max_len = 0

    def dfs(node: TreeNode, direction: str, length: int):
        """
        Performs a depth-first search to find the longest ZigZag path.

        Args:
            node: The current node being visited.
            direction: The direction of the previous step ('left' or 'right').
            length: The length of the current ZigZag path.
        """
        nonlocal max_len
        if not node:
            return

        max_len = max(max_len, length)

        if direction == 'right':
            dfs(node.left, 'left', length + 1)
            dfs(node.right, 'right', 0)  # Reset length if continuing in the same direction.
        else:  # direction == 'left'
            dfs(node.right, 'right', length + 1)
            dfs(node.left, 'left', 0)  # Reset length if continuing in the same direction

    dfs(root.left, 'left', 1)  # Start ZigZag from left
    dfs(root.right, 'right', 1) # Start ZigZag from right

    return max_len