पायथन में एक बाइनरी सर्च ट्री का सबसे कम सामान्य पूर्वज

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है। हमें दो दिए गए नोड्स के सबसे कम सामान्य पूर्वज नोड्स को खोजना होगा। दो नोड्स p और q का LCA वास्तव में पेड़ में सबसे कम नोड के रूप में होता है जिसमें p और q दोनों डीसेंटेंट होते हैं। तो अगर बाइनरी ट्री [6, 2, 8, 0, 4, 7, 9, नल, नल, 3, 5] जैसा है। पेड़ जैसा होगा -

यहां 2 और 8 का एलसीए 6 है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि पेड़ खाली है, तो अशक्त लौटें
• यदि p और q दोनों रूट के समान हैं, तो रूट वापस करें
• बाएं:=p और q का उपयोग करके रूट के बाएं उपट्री का LCA
• दाएं:=p और q का उपयोग करते हुए जड़ के दाएं उपप्रकार का LCA
• अगर बाएँ और दाएँ दोनों गैर-शून्य हैं, तो रूट लौटाएँ
• बाएं या दाएं लौटें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution():
   def lowestCommonAncestor(self, root, p, q):
      if not root:
         return None
      if p == root or q==root:
         return root
      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      if left and right:
         return root
      return left or right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         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

root = make_tree([6,2,8,0,4,7,9,None,None,3,5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)

इनपुट

[6,2,8,0,4,7,9,null,null,3,5]
2
8

आउटपुट

6