BinarySearch 0858 Sum of Two Numbers in BSTs

Problem statement

https://binarysearch.com/problems/Sum-of-Two-Numbers-in-BSTs/

Solution

We can just transform to lists and use 2sum problem.

Complexity

It is O(n + m) for time and space.

Code

class Solution:
    def solve(self, a, b, target):
        def dfs(node, res):
            if not node: return
            dfs(node.left, res)
            res.append(node.val)
            dfs(node.right, res)

        arr1, arr2 = [], []
        dfs(a, arr1)
        dfs(b, arr2)
        s1, s2 = set(arr1), set(arr2)
        for x in s1:
            if target - x in s2:
                return True
        return False