1506. Find Root of N-Ary Tree

LeetCode medium оригинал: C# #array #bit-manipulation #csharp #hash-table #leetcode #medium #search #tree

LeetCode Static

Вам даны все узлы 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.

C# решение

сопоставлено/оригинал

public class Solution {
    public Node FindRoot(IList<Node> tree) {
        HashSet<int> seen = new HashSet<int>();
        foreach (Node node in tree) {
            foreach (Node child in node.children) {
                seen.Add(child.val);
            }
        }
        Node root = null;
        foreach (Node node in tree) {
            if (!seen.Contains(node.val)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public Node FindRoot(IList<Node> tree) {
        HashSet<int> seen = new HashSet<int>();
        foreach (Node node in tree) {
            foreach (Node child in node.children) {
                seen.push_back(child.val);
            }
        }
        Node root = null;
        foreach (Node node in tree) {
            if (!seen.Contains(node.val)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public Node findRoot(List<Node> tree) {
        HashSet<Integer> seen = new HashSet<Integer>();

        for (Node node : tree) {
            for (Node child : node.children) {
                seen.add(child.val);
            }
        }

        Node root = null;
        for (Node node : tree) {
            if (!seen.contains(node.val)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

JavaScript решение

сопоставлено/оригинал

var findRoot = function(tree) {
    const seen = new Set();

    for (const node of tree) {
        for (const child of node.children) {
            seen.add(child.val);
        }
    }

    for (const node of tree) {
        if (!seen.has(node.val)) {
            return node;
        }
    }
};

Go решение

сопоставлено/оригинал

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
}

Algorithm

Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.

Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.