LeetCode Solutions Blog

Longest Univalue Path

Number: 687

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, return the length of the longest path (in terms of edges) where each node in the path has the same value. The path may or may not pass through the root.

Key Insights

Use Depth-First Search (DFS) to traverse the tree in postorder.
For each node, compute the longest path with the same value that starts from its left child and right child.
Extend the path if the child node's value equals the current node's value.
Combine the left and right paths at the current node to consider the situation where the path goes through the node.
Maintain a global variable to track the maximum path length found.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n) in the worst case due to the recursion stack.

Solution

Perform a DFS traversal of the tree. At each node, calculate the longest univalue path from its left and right children that can be connected with the current node (if the child's value is the same as the current node's value). Update a global maximum using the sum of the left and right potential paths at each node. Return the maximum edge count obtained amongst all nodes.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val           # The value of the node
        self.left = left         # Pointer to the left child
        self.right = right       # Pointer to the right child

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.max_path = 0  # Global variable to track the longest univalue path
        
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0  # Base case: no node means 0 path length
            # Recursively find the longest univalue paths in the left and right subtrees
            left_length = dfs(node.left)
            right_length = dfs(node.right)
            
            left_path = right_path = 0  # Initialize paths from left and right
            # If left child exists and value matches, extend the left path
            if node.left and node.left.val == node.val:
                left_path = left_length + 1
            # If right child exists and value matches, extend the right path
            if node.right and node.right.val == node.val:
                right_path = right_length + 1
            
            # Update the global maximum path: path may use both left and right extensions
            self.max_path = max(self.max_path, left_path + right_path)
            # Return the longer of one side which could be extended to parent's path
            return max(left_path, right_path)
        
        dfs(root)  # Start DFS from the root
        return self.max_path  # Return the longest univalue path