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

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

यहां 5 और 1 का एलसीए 3 है

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

• यदि पेड़ खाली है, तो अशक्त लौटें
• यदि 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
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
class Solution(object):
   def lowestCommonAncestor(self, root, p, q):
      if not root:
         return None
      if root.data == p or root.data ==q:
         return root
      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      if right and left:
         return root
      return right or left
ob1 = Solution()
tree = make_tree([3,5,1,6,2,0,8,None,None,7,4])
print(ob1.lowestCommonAncestor(tree, 5, 1).data)

इनपुट

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

आउटपुट

3