একটি N-ary ট্রির নোডগুলো একটি অ্যারেতে দেওয়া থাকলে, ট্রি পুনর্গঠন করে রুট নোড খুঁজে বের করতে হবে। রুট নোড থেকে প্রি-অর্ডার ট্রাভার্সাল দেখাতে হবে।
ইনপুট চিত্র অনুযায়ী, আউটপুট: [14, 27, 32, 42, 56, 65]।
সমাধানের ধাপসমূহ (Indegree কাউন্ট)
indegree := একটি ম্যাপ (ডিফল্ট 0)
প্রতিটি নোডের জন্য:
- প্রতিটি চাইল্ডের জন্য: indegree[child.val]++
প্রতিটি নোডের জন্য:
- যদি indegree[node.val] == 0, তবে সেই নোডটি রুট, রিটার্ন করুন
অন্যথায় None রিটার্ন করুন
উদাহরণ (Python)
import collections
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(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 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])
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]
