মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে এবং আমাদের ট্রির সব নোডের লোয়েস্ট কমন অ্যান্সেস্টর বের করতে বলা হয়েছে। বাইনারি ট্রিতে লোয়েস্ট কমন অ্যান্সেস্টর হল সেই নোড যা সবচেয়ে নিচে অবস্থিত এবং যার ডিসেন্ডেন্ট হিসেবে x1, x2, x3, ..., xn নোডগুলো থাকে। একটি নির্দিষ্ট নোড নিজেরাও তার ডিসেন্ডেন্ট হতে পারে। আমাদের নোডটি বের করে রিটার্ন করতে হবে। ইনপুটগুলো হল ট্রির রুট নোড এবং যেসব নোডের অ্যান্সেস্টর বের করতে হবে তার লিস্ট।
যেমন, ইনপুট যদি এমন হয়:
এবং অ্যান্সেস্টর বের করতে হবে নোডগুলো [6, 8]; তবে আউটপুট হবে 7।
আউটপুট 7, কারণ নোড ৬ এবং ৮ যেসব নোডের ডিসেন্ডেন্ট, সেগুলোর মধ্যে সবচেয়ে নিচের নোড হল ৭।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- একটি ফাংশন fn() ডিফাইন করুন। এটি node নেবে:
- যদি node null-এর মতো হয়, তবে node রিটার্ন করুন
- অন্যথায় যদি node nodes-এ উপস্থিত থাকে, তবে node রিটার্ন করুন
- left := fn(node.left), right := fn(node.right)
- যদি left এবং right null না হয়, তবে node রিটার্ন করুন
- অন্যথায়, যদি left বা right null না হয়, তবে node রিটার্ন করুন
- nodes := একটি নতুন লিস্ট
- node_list-এ থাকা প্রতিটি elem জন্য:
- search_node(root, elem) nodes-এর শেষে ইনসার্ট করুন
- nodes := nodes থেকে একটি নতুন সেট তৈরি করুন
- fn(root) রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
import collections
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if (root == None):
return None
if (root.data == element):
return root
res1 = search_node(root.left, element)
if res1:
return res1
res2 = search_node(root.right, element)
return res2
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.right)
def solve(root, node_list):
nodes = []
for elem in node_list:
nodes.append(search_node(root, elem))
nodes = set(nodes)
def fn(node):
if not node:
return node
elif node in nodes:
return node
left, right = fn(node.left), fn(node.right)
return node if left and right else left or right
return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6,8]).data)
ইনপুট
make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]
আউটপুট
7
