Question
Formatted question description: https://leetcode.ca/all/1214.html
Given two binary search trees,
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:
2 1
/ \ / \
1 4 0 3
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.
@tag-array
Algorithm
Get two ordered list, and 2 pointers to move forward for each.
Code
Java
-
import java.util.ArrayList; import java.util.List; public class Two_Sum_BSTs { // Time: O(M+N) // Space: O(logmax(M,N)) in the best case; O(max(M,N)) in the worst case. public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) { // Convert to list List<Integer> list1 = new ArrayList<>(); List<Integer> list2 = new ArrayList<>(); listByInorder(root1, list1); listByInorder(root2, list2); // Two Pointers int lo = 0, hi = list2.size() - 1; while (lo < list1.size() && hi >= 0) { // notice the condition here int sum = list1.get(lo) + list2.get(hi); if (sum == target) { return true; } else if (sum < target) { ++lo; } else { --hi; } } return false; } private void listByInorder(TreeNode root, List<Integer> list) { if (root == null) { return; } listByInorder(root.left, list); list.add(root.val); listByInorder(root.right, list); } }
-
// OJ: https://leetcode.com/problems/two-sum-bsts/ // Time: O(A + B) // Space: O(HA + HB) class Solution { void pushNodes(stack<TreeNode*> &s, TreeNode *n, bool right = false) { for (; n; n = right ? n->right : n->left) s.push(n); } public: bool twoSumBSTs(TreeNode* a, TreeNode* b, int target) { stack<TreeNode*> sa, sb; pushNodes(sa, a); pushNodes(sb, b, true); while (sa.size() && sb.size()) { int sum = sa.top()->val + sb.top()->val; if (sum == target) return true; if (sum < target) { auto n = sa.top(); sa.pop(); pushNodes(sa, n->right); } else { auto n = sb.top(); sb.pop(); pushNodes(sb, n->left, true); } } return false; } };
-
print("Todo!")