Problem statement

https://binarysearch.com/problems/Longest-Arithmetic-Sequence-Tree-Path/

Solution

Use dfs here with state (node, difference, length of path). Then we use dfs, where we try to visit the left and the right nodes and greedily construct the path.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        self.ans = 0
        def dfs(node, diff, l):
            self.ans = max(self.ans, l)
            if not node: return
            for child in filter(None, [node.left, node.right]):
                if child.val - node.val == diff:
                    dfs(child, diff, l + 1)
                else:
                    dfs(child, child.val - node.val, 2)

        dfs(root, 0, 1)
        return self.ans