Longest Univalue Path - Leetcode Solution

The Longest Univalue Path problem on LeetCode is to find the length of the longest path in a binary tree, such that all nodes on the path have the same value. The path can be any sequence of connected nodes, but it must be a path, not just a branch.

To solve this problem, we can use recursion to traverse the binary tree and keep track of the longest path as we go. We will also need to keep track of the current node's value and the length of the path from the current node to its parent.

Here is the detailed solution to the Longest Univalue Path problem on LeetCode:

Step 1: Define a helper function that traverses the binary tree and returns the longest path length and the current node's value.

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        def traverse(node):
            if not node:
                return 0, None
            left_len, left_val = traverse(node.left)
            right_len, right_val = traverse(node.right)
            length = 0
            if node.val == left_val == right_val:
                length = left_len + right_len + 2
            elif node.val == left_val:
                length = left_len + 1
            elif node.val == right_val:
                length = right_len + 1
            return length, node.val
        
        return traverse(root)[0]

Step 2: In the main function, call the helper function and return the longest path length.

In the traverse function, we first check if the current node is None. If it is None, we return 0 for the path length and None for the node value.

If the current node is not None, we recursively call the traverse function on its left and right children to get the longest path length and the node value for each child.

Next, we calculate the length of the path from the current node to its parent based on the values of the current node, its left child, and its right child. If all three nodes have the same value, we add 2 to the length of the path from the left child to the current node and the length of the path from the right child to the current node.

If only the current node and the left child have the same value, we add 1 to the length of the path from the left child to the current node. Similarly, if only the current node and the right child have the same value, we add 1 to the length of the path from the right child to the current node.

Finally, we return the length of the longest path from the current node and its value to its parent.

In the main function, we call the traverse function on the root node and return the length of the longest path.

1