মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি এবং দুটি নির্দিষ্ট নোড x এবং y দেওয়া আছে। আমাদের বাইনারি ট্রি থেকে এই দুটি নোডের লোয়েস্ট কমন অ্যান্সেস্টর বের করতে হবে। বাইনারি ট্রিতে লোয়েস্ট কমন অ্যান্সেস্টর হল সেই নোড যা সবচেয়ে নিচে অবস্থিত এবং যার ডিসেন্ডেন্ট হিসেবে x এবং y উভয় নোড থাকে। একটি নির্দিষ্ট নোড নিজেরাও তার ডিসেন্ডেন্ট হতে পারে। আমাদের নোডটি বের করে রিটার্ন করতে হবে।
যেমন, ইনপুট যদি এমন হয়:
এবং x = 2, y = 4; তবে আউটপুট হবে 3।
নোড ২ এবং ৪ যেসব নোডের ডিসেন্ডেন্ট, সেটি হল ৩। তাই ৩ রিটার্ন হবে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- একটি ফাংশন dfs() ডিফাইন করুন। এটি node নেবে:
- যদি node null-এর মতো হয়, তবে রিটার্ন করুন
- যদি node [x,y] লিস্টে থাকে, তবে:
- left := dfs(node.left)
- right := dfs(node.right)
- যদি left বা right নন-জিরো হয়, তবে ans := node এবং node রিটার্ন করুন
- left := dfs(node.left)
- right := dfs(node.right)
- যদি left এবং right null না হয়, তবে ans := node এবং node রিটার্ন করুন
- left বা right রিটার্ন করুন
- ans := dfs(root)
- ans রিটার্ন করুন
উদাহরণ
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 solve(root, x, y):
def dfs(node):
if not node:
return
if node in [x,y]:
left = dfs(node.left)
right = dfs(node.right)
if left or right:
ans = node
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
ans = node
return node
return left or right
ans = dfs(root)
return ans
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(root, search_node(root, 2), search_node(root, 4)).data)
ইনপুট
make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]), search_node(root, 2), search_node(root, 4)
আউটপুট
3
