배열에서 n-ary 트리의 노드가 주어진다고 가정합니다. 트리를 재구성하여 루트 노드를 찾아 반환해야 합니다. 전체 트리는 선주문 표기법으로 반환된 노드에서 표시되어야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은
[14, 27, 32, 42, 56, 65]
트리의 루트를 사용하여 트리의 선주문 순회를 표시합니다. 따라서 출력은 트리의 선주문 순회입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
indegree :=정수 값을 포함하는 새 맵
-
트리의 각 노드에 대해
-
노드의 자식 포인터에 있는 각 자식에 대해 다음을 수행합니다.
-
차수[자식 값] :=차수[자녀 값] + 1
-
-
-
트리의 각 노드에 대해
-
indegree[노드의 값]이 0과 같으면
-
반환 노드
-
-
-
null 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import collections
class Node:
def __init__(self, value, child = None) -> None:
self.val = value
self.children = []
if child != None:
for value in child:
self.children.append(value)
def solve(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
def treeprint(node, tree):
if node == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
tree = [node2, node1, node5, node3, node6, node4]
root = solve(tree)
print(treeprint(root, None)) 입력
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]
출력
[14, 27, 32, 42, 56, 65]