Leetcode 0687 Longest Univalue Path

Problem statement

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

Solution

Just traverse tree with dfs(node), which return longest left and right univalue paths.

Complexity

Time complexity is O(n), space is O(h).

Code

class Solution:
    def longestUnivaluePath(self, root):
        self.ans = 0
        
        def dfs(node):
            l, r = (0, 0)
            if not node: return (l, r)
            l1, r1 = dfs(node.left)
            l2, r2 = dfs(node.right)
            
            if node.right and node.right.val == node.val:
                r = 1 + max(l2, r2)     
            if node.left and node.left.val == node.val:
                l = 1 + max(l1, r1)
            
            self.ans = max(self.ans, l + r)
            return (l, r)
        
        dfs(root)
        return self.ans