1506. Find Root of N-Ary Tree

LeetCode medium original: C# #array #bit-manipulation #csharp #hash-table #leetcode #medium #search #tree

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

Вам given все узлы N-арного дерева в виде arrayа объектов Node, где каждый узел имеет уникальное значение.

return корень N-арного дерева.

Exemplo:

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# solução

correspondente/original

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++ solução

rascunho automático, revisar antes de enviar

#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 solução

correspondente/original

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 solução

correspondente/original

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 solução

correspondente/original

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) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

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

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.