Задача: 653. Two Sum IV - Input is a BST
Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.
Пример:
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
👨💻 Алгоритм:
1⃣Выполните обход BST и сохраните все значения узлов в набор.
2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.
3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.
😎 Решение:
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun findTarget(root: TreeNode?, k: Int): Boolean {
val seen = mutableSetOf<Int>()
fun find(node: TreeNode?): Boolean {
if (node == null) return false
if (seen.contains(k - node.`val`)) return true
seen.add(node.`val`)
return find(node.left) || find(node.right)
}
return find(root)
}👉Новости 👉Платформа