🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1506. Find Root of N-Ary Tree
Сложность: medium
Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.
Верните корень N-арного дерева.
Пример:
Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.
👨💻 Алгоритм:
1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.
2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.
3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.
😎 Решение
func findRoot(tree []*Node) *Node {
seen := make(map[int]struct{})
for _, node := range tree {
for _, child := range node.Children {
seen[child.Val] = struct{}{}
}
}
for _, node := range tree {
if _, found := seen[node.Val]; !found {
return node
}
}
return nil
}
Ставь 👍 и забирай 📚 Базу знаний
