Задача: 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.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private void Dfs(TreeNode node, HashSet<int> nodeSet) {
        if (node == null) return;
        Dfs(node.left, nodeSet);
        nodeSet.Add(node.val);
        Dfs(node.right, nodeSet);
    }

    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        HashSet<int> nodeSet1 = new HashSet<int>();
        HashSet<int> nodeSet2 = new HashSet<int>();
        Dfs(root1, nodeSet1);
        Dfs(root2, nodeSet2);
        
        foreach (int value1 in nodeSet1) {
            if (nodeSet2.Contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
}

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