链接：查找两棵二叉搜索树之和
方法一
遍历第一棵树，每遍历一个节点，在第二棵树中查找，时间复杂度
# 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 []
