链接：查找两棵二叉搜索树之和

方法一

遍历第一棵树，每遍历一个节点，在第二棵树中查找，时间复杂度

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        if not (root1 and root2):
            return False
          
        q = deque()
        q.append(root1)
        while q:
            node = q.popleft()
            has_res = self.findInTree(root2, target-node.val)
            if has_res:
                return True
            else:
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return False

    def findInTree(self, root, target):
        if not root:
            return False
        if root.val == target:
            return True
        elif root.val < target:
            return self.findInTree(root.right, target)
        else:
            return self.findInTree(root.left, target)

方法二

先用中序遍历，将二叉搜索树转换成两个有序数组，然后使用两个指针，一个指向第一个数组的头部，一个指向第二个数组的尾部，通过移动指针来寻找结果。

其中中序遍历可以一行代码实现：

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

完整代码如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        if not (root1 and root2):
            return False

        nums1 = self.inorder(root1)
        nums2 = self.inorder(root2)

        m = len(nums1)
        n = len(nums2)
        i = 0
        j = n-1
        while i < m and j >= 0:
            if nums1[i] + nums2[j] < target:
                i += 1
            elif nums1[i] + nums2[j] == target:
                return True
            else:
                j -= 1
        
        return False
          
    def inorder(self, root):
        return self.inorder(root.left) + [root.val] + self.inorder(root.right) if root else []