पायथन में समान बाएँ और दाएँ उपप्रकार वाले सबसे बड़े उपट्री का पता लगाएं

मान लीजिए कि हमारे पास एक बाइनरी ट्री है; हमें सबसे बड़ा सबट्री ढूंढना है जिसमें समान बाएँ और दाएँ सबट्री हों। पसंदीदा समय जटिलता O(n) है।

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

तो आउटपुट होगा

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

• फ़ंक्शन को हल करें () परिभाषित करें। यह रूट लेगा, एनकोड करेगा, मैक्ससाइज करेगा, मैक्सनोड करेगा

• अगर जड़ कोई नहीं है, तो

  • वापसी 0

• left_list :=एक रिक्त स्ट्रिंग वाली सूची

• right_list :=एक रिक्त स्ट्रिंग वाली सूची

• ls :=हल करें (root.left, left_list, maxSize, maxNode)

• rs :=हल करें (root.right, right_list, maxSize, maxNode)

• आकार :=ls + rs + 1

• अगर left_list[0], right_list[0] के समान है, तो

  • यदि आकार> अधिकतम आकार [0], तो

    • अधिकतम आकार [0] :=आकार

    • मैक्सनोड [0]:=रूट

• सांकेतिक शब्दों में बदलना [0]:=सांकेतिक शब्दों में बदलना [0] संक्षिप्त "|" संयोजित करें left_list[0] संक्षिप्त करें "|"

• सांकेतिक शब्दों में बदलना [0]:=सांकेतिक शब्दों में बदलना [0] संक्षिप्त "|" concatenate str(root.data) concatenate "|"

• सांकेतिक शब्दों में बदलना [0]:=सांकेतिक शब्दों में बदलना [0] संक्षिप्त "|" सम्‍मिलित करें right_list[0] संक्षिप्त करें "|"

• वापसी का आकार

• मुख्य विधि से, निम्न कार्य करें -

• अधिकतम:=[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]