Сложность: easy
Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.
Дерево cloned является копией оригинального дерева.
Верните ссылку на тот же узел в дереве cloned.
Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.
Пример:
Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.
👨💻 Алгоритм:
1⃣Добавьте корень в очередь.
2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь.
3⃣Верните ссылку на найденный целевой узел.
😎 Решение:
class Solution:
def getTargetCopy(self, original, cloned, target):
queue_o = [original]
queue_c = [cloned]
while queue_o:
node_o = queue_o.pop(0)
node_c = queue_c.pop(0)
if node_o is target:
return node_c
if node_o.left:
queue_o.append(node_o.left)
queue_c.append(node_c.left)
if node_o.right:
queue_o.append(node_o.right)
queue_c.append(node_c.right)
return None
Ставь 👍 и забирай 📚 Базу знаний