मान लीजिए, हमें एक n-ary ट्री दिया गया है जिसका रूट 'root' है। हमें पूरे n-ary ट्री की एक कॉपी बनानी है और दोनों ट्री का प्रीऑर्डर ट्रैवर्सल करना है। कॉपी किए गए ट्री को दूसरे रूट नोड का उपयोग करके स्टोर करना है। ट्री की नोड संरचना नीचे दी गई है:
Node:
value:
children:
इसलिए, यदि इनपुट निम्न ट्री है:
तो आउटपुट होगा:
[14, 27, 32, 42, 56, 65]
इनपुट ट्री और आउटपुट ट्री का प्रीऑर्डर प्रतिनिधित्व समान होगा क्योंकि ट्री की एक सटीक कॉपी बनाई गई है।
हल करने के चरण
- यदि root खाली है, तो root वापस करें
- head := root के मान के साथ एक नया नोड
- q := root और head वाले तत्वों का एक नया deque
- जब q खाली नहीं है:
- node := q से पहला तत्व पॉप करें
- cloned := q से पहला तत्व पॉप करें
- node.children में प्रत्येक chld के लिए:
- new_n := chld के मान वाला एक नया नोड
- cloned के children में new_n जोड़ें
- q के अंत में chld और new_n डालें
- head वापस करें
उदाहरण (Python)
from queue import deque
class Node:
def __init__(self, value, child=None) -> None:
self.val = value
self.children = []
if child is not 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 is None:
tree.append("None")
return tree
if tree is 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]
