687. Longest Univalue Path

Medium

Problem:

Find the longest path with the same value.

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

https://leetcode.com/problems/longest-univalue-path/

Solution:

You can solve this by descending to the leaf nodes of the tree using DFS and then backtracking while accumulating distance when the values match.

1. For both left and right child nodes, check if they have the same value as the current node (i.e., the parent node). If so, increment the distance by 1 for each.

2. The path will be the sum of the distances between the left and right child nodes.

3. Lastly, pass the calculated distance up to the parent node. Since the parent node of the current node can't connect both left and right child nodes simultaneously, return the larger value between them as the status value. This is because, if you can only visit one place, it's better to visit the longer one.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    path: int = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node: TreeNode) -> int:
            if node is None:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)

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

            self.path = max(self.path, left + right)

            return max(left, right)
        
        dfs(root)
        return self.path