BinarySearch 0338 Longest Even Sum Path

Problem statement

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

Solution

Use dfs, where for each node we return two values: e, o: the longest path with even and with odd sums, going from this node down. Then depending on we have odd or even value of node we recalculate values and also update answer: wihch can be one of 3 types for even value:

1. Even sum path in the left part, even sum path in the right path
2. Odd sum path in the left part, odd sum path in the right path
3. Path which have only one part, that is we start from node and go down.

Similar logic is for odd value of node.

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, -float("inf"))
            e1, o1 = dfs(node.left)
            e2, o2 = dfs(node.right)
            if node.val % 2 == 0:
                e, o = max(e1, e2) + 1, max(o1, o2) + 1
                self.ans = max(self.ans, e1 + e2 + 1, o1 + o2 + 1, e)
            else:
                e, o = max(o1, o2) + 1, max(e1, e2) + 1
                self.ans = max(self.ans, e1 + o2 + 1, e2 + o1 + 1, e)
            
            return e, o

        dfs(root)
        return self.ans