Problem statement

https://binarysearch.com/problems/Longest-Even-Value-Path/

Solution

Use dfs which answer question (longest left path, longest right path) for given node. This is similar like what we did when we look for diameter.

Complexity

It is O(n) for time and O(h) for space.

Code

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

        dfs(root)
        return self.ans