Пара из двух деревьев поиска

Средняя

Даны корни first и second двух двоичных деревьев поиска и число goal. В каждом дереве все значения различны: для любой вершины значения в её левом поддереве меньше, а в правом — больше её собственного. Верните True, если можно выбрать одну вершину из первого дерева и одну из второго так, чтобы сумма их значений равнялась goal, и False иначе.

Пример 1

first=tree_node([6, 2, 9]), second=tree_node([4, 1, 8]), goal=10 → True

6 из первого дерева и 4 из второго дают 10.

Пример 2

first=tree_node([3, 1, 5]), second=tree_node([20, 10, 30]), goal=12 → False

Возможные суммы: 11, 13, 15, 21, 23, 25, 31, 33, 35 — числа 12 среди них нет.

Пример 3

first=tree_node([-5]), second=tree_node([0, -7, None, None, -2]), goal=-7 → True

Ограничения

1 ≤ число вершин в каждом дереве ≤ 5·10⁴
-10⁹ ≤ Node.val ≤ 10⁹
-10⁹ ≤ goal ≤ 10⁹
Оба дерева — корректные деревья поиска

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Stack Tree Depth-First Search Binary Search Tree Two Pointers Binary Search Binary Tree

Вход

first=tree_node([6, 2, 9]), second=tree_node([4, 1, 8]), goal=10

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 69 тестов на сервере, включая скрытые.