루트가 우리에게 '루트'로 주어진 n진 트리가 제공되었다고 가정합니다. 우리는 완전한 n-ary 이진 트리의 복사본을 만들고 두 트리의 사전 순서 순회를 수행해야 합니다. 복사된 트리는 다른 루트 노드를 사용하여 저장해야 합니다. 트리의 노드 구조는 다음과 같습니다. -
Node: value : <integer> children : <array>
따라서 입력이 다음과 같으면
, 출력은
[14, 27, 32, 42, 56, 65]
입력 트리 및 출력 트리의 사전 주문 표현은 생성된 트리의 정확한 사본과 동일합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
루트가 비어 있지 않으면
-
루트 반환
-
-
head :=root 값을 가진 새 노드
-
q :=루트와 헤드 요소를 포함하는 새로운 데크
-
q가 비어 있지 않은 동안 수행
-
node :=q에서 첫 번째 요소 팝
-
cloned :=q에서 첫 번째 요소 팝
-
node.children의 각 chld에 대해
-
new_n :=chld 값을 포함하는 새 노드
-
복제된 자식에 new_n 추가
-
q의 끝에 chld 및 new_n 삽입
-
-
-
머리 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from queue import deque
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(root):
if not root:
return root
head = Node(root.val)
q = deque([(root, head)])
while q:
node, cloned = q.popleft()
for chld in node.children:
new_n = Node(chld.val)
cloned.children.append(new_n)
q.append((chld,new_n))
return head
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])
root = node1
copynode = solve(root)
print(treeprint(copynode, None)) 입력
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) root = node1
출력
[14, 27, 32, 42, 56, 65]