पायथन में सबसे गहरी पत्तियों का सबसे कम सामान्य पूर्वज

मान लीजिए कि हमारे पास एक रूटेड बाइनरी ट्री है, हमें इसकी सबसे गहरी पत्तियों के सबसे कम सामान्य पूर्वज को वापस करना होगा। हमें यह ध्यान रखना होगा कि -

• बाइनरी ट्री का नोड एक लीफ नोड होता है यदि और केवल अगर उसके कोई बच्चे नहीं हैं

• पेड़ की जड़ की गहराई 0 होती है, और जब एक नोड की गहराई d होती है, तो उसके प्रत्येक बच्चे की गहराई d+1 होती है।

• नोड ए में नोड्स के सेट एस के सबसे कम सामान्य पूर्वज सबसे बड़ी गहराई के साथ जैसे कि एस में प्रत्येक नोड रूट ए के साथ उपट्री में है।

अगर इनपुट [1,2,3,4,5],

तो आउटपुट [2,4,5]

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

• हल () नामक एक विधि को परिभाषित करें, यह नोड लेगा, यह निम्नानुसार काम करेगा -

• यदि नोड मौजूद नहीं है, तो [0, कोई नहीं] के साथ एक सूची लौटाएं

• यदि बाएँ और दाएँ उपप्रकार नोड से खाली हैं, तो एक सूची लौटाएँ [1, कोई नहीं]

• d1, l:=हल करें (नोड के बाएँ), d2, r:=हल करें (नोड का दाएँ)

• अगर d1> d2 , तो मानों के साथ एक सूची लौटाएं [d1 + 1, l]

• अन्यथा जब d2> d1, फिर मानों के साथ एक सूची लौटाएं [d2 + 1, r]

• मानों के साथ एक सूची लौटाएं [d1 + 1, नोड]

• मुख्य विधि में, हम प्रदर्शन करेंगे -

• सूची:=हल (रूट)

• वापसी सूची[1]

उदाहरण (पायथन)

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

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 print_tree(root):
   #print using inorder traversal
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def lcaDeepestLeaves(self, root):
      return self.solve(root)[1]
   def solve(self,node):
      if not node:
         return [0,None]
      if not node.left and not node.right:
         return [1,node]
      d1,l = self.solve(node.left)
      d2,r = self.solve(node.right)
      if d1>d2:
         return [d1+1,l]
      elif d2>d1:
         return [d2+1,r]
      return [d1+1,node]
ob = Solution()
root = make_tree([1,2,3,4,5])
print_tree(ob.lcaDeepestLeaves(root))

इनपुट

[1,2,3,4,5]

आउटपुट

4, 2, 5,