1214. Two Sum BSTs

Posted on Edited on In

1214. Two Sum BSTs

Description

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:

1
2
3
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.

Example 2:

1
2
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Constraints:

  • The number of nodes in each tree is in the range [1, 5000].
  • -10^9 <= Node.val, target <= 10^9

Hints/Notes

  • first get the sorted array, then 2sum
  • premium

Solution

Language: C++

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        vector<int> v1 = traverse(root1);
        vector<int> v2 = traverse(root2);
        int i = 0, j = v2.size() - 1;
        while (i < v1.size() && j >= 0) {
            int sum = v1[i] + v2[j];
            if (sum == target) {
                return true;
            } else if (sum < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }

    vector<int> traverse(TreeNode* root) {
        if (!root) {
            return {};
        }
        auto l = traverse(root->left);
        auto r = traverse(root->right);

        l.push_back(root->val);
        l.insert(l.end(), r.begin(), r.end());
        return l;
    }
};