একটি N-ary ট্রি দেওয়া থাকলে তার ডায়ামিটার বের করতে হবে। ট্রির ডায়ামিটার হলো যেকোনো دوটি লিফ নোডের মধ্যবর্তী সর্বদীর্ঘ পথ। পথের দৈর্ঘ্য (এজ সংখ্যা) রিটার্ন করতে হবে।
উদাহরণ ট্রি চিত্রে দেখানো হয়েছে। আউটপুট: 3। ডায়ামিটার পথ: 27→14, 14→42, 42→56 (বা 42→65)।
সমাধানের ধাপসমূহ (DFS + গ্লোবাল ভেরিয়েবল)
ans := 1
depth(root) ফাংশন ডিফাইন করুন:
- যদি root খালি হয়: return 0
- children = [0, 0]
- temp_children = [depth(child) for child in root.children]
- যদি temp_children খালি না হয়: children = temp_children
- ans = max(ans, sum(sorted(children)[-2:]) + 1)
- return max(children) + 1
depth(root) কল করুন
return ans - 1
উদাহরণ (Python)
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)
ans = 1
def solve(root):
def depth(root):
global ans
if not root:
return 0
children = [0, 0]
temp_children = [depth(child) for child in root.children]
if len(temp_children) > 0:
children = temp_children
ans = max(ans, sum(sorted(children)[-2:]) + 1)
return max(children) + 1
depth(root)
return ans - 1
# ট্রি তৈরি
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
print(solve(root))
ইনপুট
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
আউটপুট
3
