Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.
The number of nodes in each tree is in the range [1, 5000].
-109 <= Node.val, target <= 109
Solutions
Solution 1: In-order Traversal + Two Pointers
We perform in-order traversals on the two trees separately, obtaining two sorted arrays $nums[0]$ and $nums[1]$. Then we use a two-pointer method to determine whether there exist two numbers whose sum equals the target value. The two-pointer method is as follows:
Initialize two pointers $i$ and $j$, pointing to the left boundary of array $nums[0]$ and the right boundary of array $nums[1]$ respectively;
Each time, compare the sum $x = nums[0][i] + nums[1][j]$ with the target value. If $x = target$, return true; otherwise, if $x \lt target$, move $i$ one step to the right; otherwise, if $x \gt target$, move $j$ one step to the left.
The time complexity is $O(m + n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the number of nodes in the two trees respectively.
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */functwoSumBSTs(root1*TreeNode,root2*TreeNode,targetint)bool{nums:=[2][]int{}vardfsfunc(*TreeNode,int)dfs=func(root*TreeNode,iint){ifroot==nil{return}dfs(root.Left,i)nums[i]=append(nums[i],root.Val)dfs(root.Right,i)}dfs(root1,0)dfs(root2,1)i,j:=0,len(nums[1])-1fori<len(nums[0])&&j>=0{x:=nums[0][i]+nums[1][j]ifx==target{returntrue}ifx<target{i++}else{j--}}returnfalse}