Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

👨‍💻 Алгоритм:

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
void dfs(TreeNode* node, unordered_set& nodeSet) {
if (!node) return;
dfs(node->left, nodeSet);
nodeSet.insert(node->val);
dfs(node->right, nodeSet);
}

public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
unordered_set nodeSet1, nodeSet2;
dfs(root1, nodeSet1);
dfs(root2, nodeSet2);

for (int value1 : nodeSet1) {
if (nodeSet2.count(target - value1)) {
return true;
}
}

return false;
}
};

Ставь 👍 и забирай 📚 Базу знаний