Сложность: 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 {
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
Deque<TreeNode> queue_o = new ArrayDeque<>();
queue_o.offer(original);
Deque<TreeNode> queue_c = new ArrayDeque<>();
queue_c.offer(cloned);
while (!queue_o.isEmpty()) {
TreeNode node_o = queue_o.poll();
TreeNode node_c = queue_c.poll();
if (node_o == target) {
return node_c;
}
if (node_o.left != null) {
queue_o.offer(node_o.left);
queue_c.offer(node_c.left);
}
if (node_o.right != null) {
queue_o.offer(node_o.right);
queue_c.offer(node_c.right);
}
}
return null;
}
}Ставь 👍 и забирай 📚 Базу знаний