একটি N-ary ট্রির রুট দেওয়া থাকলে, পুরো ট্রির এক্স্যাক্ট কপি (ডিপ কপি) তৈরি করতে হবে এবং দুটি ট্রির প্রি-অর্ডার ট্রাভার্সাল প্রিন্ট করতে হবে। কপি করা ট্রি অন্য একটি রুট নোডে সংরক্ষিত হবে।
নোড স্ট্রাকচার: value (ইন্টিজার), children (অ্যারে)।
ইনপুট ট্রি চিত্র অনুযায়ী, আউটপুট: [14, 27, 32, 42, 56, 65]। মূল ট্রি এবং কপি করা ট্রির প্রি-অর্ডার একই হবে।
সমাধানের ধাপসমূহ (BFS + Queue)
যদি root খালি হয়: return root
head := নতুন নোড root.val দিয়ে
q := deque যাতে (root, head) জোড়া থাকে
যখন q খালি নয়:
- node, cloned = q.popleft()
- প্রতিটি child-এর জন্য:
- new_n = Node(child.val)
- cloned.children.append(new_n)
- q.append((child, 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]
