পাইথনে অভিন্ন বাম এবং ডান সাবট্রি সহ বৃহত্তম সাবট্রি খুঁজুন

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদেরকে অভিন্ন বাম এবং ডান সাবট্রি সহ বৃহত্তম সাবট্রি খুঁজে বের করতে হবে। পছন্দের সময় জটিলতা হল O(n)।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি রুট, এনকোড, maxSize, maxNode

  নেবে

• যদি রুট কোনটি না হয়, তাহলে

  • রিটার্ন 0

• left_list :=একটি ফাঁকা স্ট্রিং সহ তালিকা

• right_list :=একটি ফাঁকা স্ট্রিং সহ তালিকা

• ls :=সমাধান করুন(root.left, left_list, maxSize, maxNode)

• rs :=সমাধান (root.right, right_list, maxSize, maxNode)

• আকার :=ls + rs + 1

• যদি বাম_তালিকা[0] ডান_তালিকা[0] এর মত হয়, তাহলে

  • যদি সাইজ> maxSize[0], তারপর

    • maxSize[0] :=আকার

    • maxNode[0] :=রুট

• encode[0] :=encode[0] concatenate "|" concatenate left_list[0] concatenate "|"

• encode[0] :=encode[0] concatenate "|" concatenate str(root.data) concatenate "|"

• encode[0] :=encode[0] concatenate "|" concatenate right_list[0] concatenate "|"

• রিটার্ন সাইজ

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• সর্বোচ্চ :=[0]

• এনকোড :=একটি ফাঁকা স্ট্রিং সহ তালিকা

• সমাধান (নোড, এনকোড, সর্বোচ্চ, ম্যাক্সনোড)

• সর্বোচ্চ রিটার্ন করুন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
   if (root == None):
      return 0
   left_list = [""]
   right_list = [""]
   ls = solve(root.left, left_list, maxSize, maxNode)
   rs = solve(root.right, right_list, maxSize, maxNode)
   size = ls + rs + 1
   if (left_list[0] == right_list[0]):
      if (size > maxSize[0]):
         maxSize[0] = size
         maxNode[0] = root
   encode[0] = encode[0] + "|" + left_list[0] + "|"
   encode[0] = encode[0] + "|" + str(root.data) + "|"
   encode[0] = encode[0] + "|" + right_list[0] + "|"

   return size

def largestSubtree(node, maxNode):
   maximum = [0]
   encode = [""]
   solve(node, encode, maximum,maxNode)
   return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree",maxNode[0].data)
print("and its size is ", maximum)

ইনপুট

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

আউটপুট

Root of largest sub-tree 70
and its size is [7]