Longest Univalue Path

Question (LC.687)

Given the root of a binary tree, find the length of the longest univalue path. An univalue path is a path between any two nodes where all the nodes have the same value. The length of the path is the number of edges.

Example

Input: [5,4,5,1,1,5]
Output: 2

Input: [1,4,5,4,4,5]
Output: 2

Input: [1,null,1,1,1,1,1,1]
Expected: 4

The last example is a good one. Same value nodes can only connect in one direction but not both.

Analysis

Divide and conquer is build for these path related problems. The return type needs to hold a couple info including the longest univalue path so far, the current univalue path, and the current value.

Code

class Solution:
    
    class ResultType:
        def __init__(self, curVal, curLen, maxLen):
            self.curVal = curVal
            self.curLen = curLen
            self.maxLen = maxLen
    
    
    def longestUnivaluePath(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        return self.pathHelper(root).maxLen - 1
        
    
    def pathHelper(self, node: TreeNode) -> ResultType:
        
        # base 
        if node is None:
            return self.ResultType(None, 0, 0)
        
        # divide 
        leftTree = self.pathHelper(node.left)
        rightTree = self.pathHelper(node.right)
        
        # merge 
        
        # compute current length 
        
        curLen = 1
        combinedLen = 1
        
        if leftTree.curVal == node.val:
            curLen = max(curLen, leftTree.curLen + 1)
            combinedLen += leftTree.curLen
        
        if rightTree.curVal == node.val:
            curLen = max(curLen, rightTree.curLen + 1)
            combinedLen += rightTree.curLen
        
        
        # compute max length 
        
        maxLen = max(combinedLen, leftTree.maxLen, rightTree.maxLen)
        
        return self.ResultType(node.val, curLen, maxLen)

Complexity

Time O(n)

Space O(n)