Introduction

In this blog post, we will explore how to solve the LeetCode problem "687" 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

Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root. The length of the path between two nodes is represented by the number of edges between them. Example 1: Input: root = [5,4,5,1,1,null,5] Output: 2 Explanation: The shown image shows that the longest path of the same value (i.e. 5). Example 2: Input: root = [1,4,5,4,4,null,5] Output: 2 Explanation: The shown image shows that the longest path of the same value (i.e. 4). Constraints: The number of nodes in the tree is in the range [0, 104]. -1000 <= Node.val <= 1000 The depth of the tree will not exceed 1000.

Explanation

Here's the approach:

• Recursive Depth-First Search: Traverse the tree using a recursive DFS approach.
• Path Length Calculation: For each node, calculate the lengths of paths extending from it to its left and right children, only if the child's value matches the node's value.

• Update Max Length: Keep track of the maximum path length encountered so far during the traversal.

• 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 (due to recursion stack). In the worst-case scenario (skewed tree), H can be equal to N. In the best case (balanced tree), H will be O(log N).

Code

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

def longest_univalue_path(root: TreeNode) -> int:
    """
    Finds the length of the longest path where each node has the same value.

    Args:
        root: The root of the binary tree.

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

    max_length = 0

    def dfs(node: TreeNode) -> int:
        """
        Performs a depth-first search to calculate the length of the path.

        Args:
            node: The current node being visited.

        Returns:
            The length of the longest univalue path starting from the current node.
        """
        nonlocal max_length

        if not node:
            return 0

        left_length = dfs(node.left)
        right_length = dfs(node.right)

        arrow_left = 0
        arrow_right = 0

        if node.left and node.left.val == node.val:
            arrow_left = left_length + 1
        if node.right and node.right.val == node.val:
            arrow_right = right_length + 1

        max_length = max(max_length, arrow_left + arrow_right)

        return max(arrow_left, arrow_right)

    dfs(root)
    return max_length