方法一
遍歷第一棵樹(shù)鸠按，每遍歷一個(gè)節(jié)點(diǎn)，在第二棵樹(shù)中查找博个，時(shí)間復(fù)雜度
# 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)
方法二
先用中序遍歷棘利，將二叉搜索樹(shù)轉(zhuǎn)換成兩個(gè)有序數(shù)組，然后使用兩個(gè)指針，一個(gè)指向第一個(gè)數(shù)組的頭部穆咐，一個(gè)指向第二個(gè)數(shù)組的尾部祖能，通過(guò)移動(dòng)指針來(lái)尋找結(jié)果闲孤。
其中中序遍歷可以一行代碼實(shí)現(xiàn)：
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 []
