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

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private fun dfs(node: TreeNode?, nodeSet: MutableSet<Int>) {
        if (node == null) return
        dfs(node.left, nodeSet)
        nodeSet.add(node.`val`)
        dfs(node.right, nodeSet)
    }

    fun twoSumBSTs(root1: TreeNode?, root2: TreeNode?, target: Int): Boolean {
        val nodeSet1 = mutableSetOf<Int>()
        val nodeSet2 = mutableSetOf<Int>()
        dfs(root1, nodeSet1)
        dfs(root2, nodeSet2)
        
        for (value1 in nodeSet1) {
            if (nodeSet2.contains(target - value1)) {
                return true
            }
        }
        
        return false
    }
}

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