🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1490. Clone N-ary Tree
Сложность: medium
Дан корень N-арного дерева, верните глубокую копию (клон) дерева.
Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.
class Node {
public int val;
public List children;
}
Сериализация входных данных N-арного дерева представлена в порядке обхода по уровням, каждая группа детей разделена значением null (см. примеры).
Пример:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
👨💻 Алгоритм:
1⃣Базовый случай:
Проверить, является ли входной узел null. Если да, вернуть null.
2⃣Копирование узла:
Создать новый узел с таким же значением, как у входного узла.
3⃣Рекурсивное клонирование детей:
Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла.
Вернуть клонированный узел.
😎 Решение:
class Node {
public var val: Int
public var children: [Node]
public init(_ val: Int) {
self.val = val
self.children = []
}
}
class Solution {
func cloneTree(_ root: Node?) -> Node? {
guard let root = root else {
return nil
}
let nodeCopy = Node(root.val)
for child in root.children {
nodeCopy.children.append(cloneTree(child)!)
}
return nodeCopy
}
}
Ставь 👍 и забирай 📚 Базу знаний
