बाइनरी ट्री में दिए गए नोड्स के लोएस्ट कॉमन एंसेस्टर (LCA) को रिकर्सिव DFS से ढूंढें।
एल्गोरिदम
- रिकर्सिव फंक्शन
fn(node)जो नोड या None रिटर्न करता है। - अगर नोड टारगेट नोड्स सेट में है, तो नोड रिटर्न करें।
- लेफ्ट और राइट सबट्री पर रिकर्स करें।
- अगर दोनों नॉन-None रिटर्न करें, तो वर्तमान नोड LCA है।
- अन्यथा जो भी नॉन-None है उसे रिटर्न करें।
- सभी टारगेट नोड्स को सेट में डालकर
fn(root)कॉल करें।
उदाहरण कोड
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def solve(root, node_list):
nodes = set()
for elem in node_list:
nodes.add(search_node(root, elem))
def fn(node):
if not node:
return node
if 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)
# टेस्ट: ट्री [5,3,7,2,4,6,8], नोड्स [6,8] -> LCA = 7
इनपुट/आउटपुट
इनपुट: ट्री [5,3,7,2,4,6,8], नोड्स [6,8]
आउटपुट: 7
