Longest Univalue Path

Introduction

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.

tree-node.py

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

Solutions

1. Using DFS

This solution finds the longest path in a binary tree where all nodes in the path have the same value. It traverses each node to determine the longest sequence of connected nodes with identical values.

main.py

def longest_univalue_path(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    max_length = 0

    def dfs(node: TreeNode) -> int:
        nonlocal max_length
        if not node:
            return 0

        left_path = dfs(node.left)
        right_path = dfs(node.right)

        if node.left and node.left.val == node.val:
            left_path += 1
        else:
            left_path = 0
        if node.right and node.right.val == node.val:
            right_path += 1
        else:
            right_path = 0

        max_length = max(max_length, left_path + right_path)
        return max(left_path, right_path)

    dfs(root)
    return max_length

Introduction

Solutions

1. Using DFS

References