Сложность: medium
Дано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null.
Верните глубокую копию дерева.
Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.
Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.
Пример:
Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.
👨💻 Алгоритм:
1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.
2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.
3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.
😎 Решение:
class Node {
var val: Int
var left: Node?
var right: Node?
var random: Node?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
self.random = nil
}
}
class NodeCopy {
var val: Int
var left: NodeCopy?
var right: NodeCopy?
var random: NodeCopy?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
self.random = nil
}
}
class Solution {
private var newOldPairs = [Node: NodeCopy]()
private func deepCopy(_ root: Node?) -> NodeCopy? {
guard let root = root else { return nil }
let newRoot = NodeCopy(root.val)
newRoot.left = deepCopy(root.left)
newRoot.right = deepCopy(root.right)
newOldPairs[root] = newRoot
return newRoot
}
private func mapRandomPointers(_ oldNode: Node?) {
guard let oldNode = oldNode else { return }
if let newNode = newOldPairs[oldNode] {
newNode.random = newOldPairs[oldNode.random]
mapRandomPointers(oldNode.left)
mapRandomPointers(oldNode.right)
}
}
func copyRandomBinaryTree(_ root: Node?) -> NodeCopy? {
let newRoot = deepCopy(root)
mapRandomPointers(root)
return newRoot
}
}Ставь 👍 и забирай 📚 Базу знаний