1214. Two Sum BSTs
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:(Image shows two binary search trees. Tree 1 has root 2, left child 1, right child 4. Tree 2 has root 1, left child 0, right child 3.)
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <iostream>
#include <vector>
class Solution {
public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
std::vector<int> array1, array2;
DFS(root1, array1);
DFS(root2, array2);
int m = array1.size();
int n = array2.size();
for (int a = 0, b = n - 1; a < m && b >= 0;) {
int cur = array1[a] + array2[b];
if (cur == target) {
return true;
}
else if (cur > target) {
--b;
}
else {
++a;
}
}
return false;
}
private:
void DFS(TreeNode* node, std::vector<int>& array) {
if (node->left != nullptr) {
DFS(node->left, array);
}
array.push_back(node->val);
if (node->right != nullptr) {
DFS(node->right, array);
}
}
};
|
