पायथन का उपयोग करके बाइनरी ट्री के सबसे कम सामान्य पूर्वज का पता लगाने का कार्यक्रम

मान लीजिए, हमें एक बाइनरी ट्री दिया गया है और दो विशिष्ट नोड x और y भी दिए गए हैं। हमें बाइनरी ट्री से दो नोड्स के सबसे कम सामान्य पूर्वज का पता लगाना है। बाइनरी ट्री में सबसे कम सामान्य पूर्वज सबसे निचला नोड होता है, जिसके दोनों नोड x और y वंशज होते हैं। साथ ही, एक विशेष नोड स्वयं का वंशज भी हो सकता है। हमें नोड ढूंढना है और इसे आउटपुट के रूप में वापस करना है।

तो, अगर इनपुट पसंद है

और एक्स =2, वाई =4; तो आउटपुट 3 होगा।

जिस नोड के नोड 2 और 4 के वंशज हैं, वह 3 है। तो, 3 वापस आ जाएगा।

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

फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा
- यदि नोड शून्य के समान है, तो
  - वापसी
- यदि नोड सूची में मौजूद है [x,y], तो
  - बाएँ:=dfs (नोड के बाएँ)
  - दाएँ:=dfs (नोड के दाएँ)
  - अगर बाएँ या दाएँ गैर-शून्य हैं, तो
    - उत्तर:=नोड
    - वापसी नोड
- बाएँ:=dfs (नोड के बाएँ)
- दाएँ:=dfs (नोड के दाएँ)
- यदि बाएँ और दाएँ शून्य नहीं हैं, तो
  - उत्तर:=नोड
  - वापसी नोड
- बाएं या दाएं लौटें
उत्तर:=डीएफएस (रूट)
वापसी उत्तर

उदाहरण

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)