2주 차 보너스 - N-Ary 트리의 루트 찾기

문제

You are given all the nodes of an N-ary tree as an array of Node objects, where each node has a unique value.

Return the root of the N-ary tree.

맞춤형 테스트:

N항 트리는 각 자식 그룹이 null 값으로 구분되는 수준 순회에 표시된 대로 직렬화할 수 있습니다(예제 참조).



예를 들어 위의 트리는 [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] 로 직렬화됩니다.

테스트는 다음과 같은 방식으로 수행됩니다.

입력 데이터는 트리의 직렬화로 제공되어야 합니다.

드라이버 코드는 직렬화된 입력 데이터에서 트리를 구성하고 각Node 개체를 임의의 순서로 배열에 넣습니다.

드라이버 코드는 배열을 findRoot 로 전달하고 함수는 배열에서 루트Node 개체를 찾아 반환해야 합니다.

드라이버 코드는 반환된 Node 객체를 가져와 직렬화합니다. 직렬화된 값과 입력 데이터가 같으면 테스트가 통과됩니다.

예 1:

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.

예 2:

Input: tree = [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, 5 * 104] 사이입니다.

각 노드에는 고유한 값이 있습니다.

후속 조치:

선형 시간 알고리즘을 사용하여 일정한 공간 복잡도에서 이 문제를 해결할 수 있습니까?

내 테스트

나는 이것에 대한 테스트를 작성하지 않았습니다.

내 솔루션

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':        
        c = {}
        n = {}
        for node in tree:            
            n[node.val] = node
            if node.children is not None:
                for ch in node.children:                    
                    c[ch.val] = True
        for k in n:
            if k not in c:
                return n[k]
        return None

분석

내 해설

나는 몇 분 안에 이것을했고 매우 게으르다. 나는 내 솔루션이 훌륭한 솔루션이 아니라고 확신합니다.

트리의 루트 노드에 대해 우리가 알고 있는 한 가지 사실은 다른 트리의 자식일 수 없다는 것입니다. 이를 감안할 때 모든 자식 노드 값을 해시 맵에 저장할 수 있고 모든 노드를 맵에 저장할 수 있습니다. 그런 다음 하위 맵에서 각 노드 값을 조회할 수 있습니다. 그 중 하나가 없으면 루트여야 합니다.

이것은 나에게 정말 해키 솔루션처럼 보이지만 오늘 이미 한 가지 도전을 수행했으며 이것을 개선할 에너지가 없습니다. 적어도 분석에서 너무 나쁘게 수행되지는 않습니다.